/*
 * -------------------------------------------------------------------------
 * THE rxpoly LIBRARY, A LIBRARY FOR WORKING WITH REGEXPS IN POLYNOMIAL TIME
 * -------------------------------------------------------------------------
 * Copyright (C)	Matěj Korvas	2010
 * (email: matej.korvas@gmail.com)
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef DEBUG
#define DEBUG
#endif

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <wchar.h>
#include <search.h>
#include <wctype.h>
#include <errno.h>
#ifdef DEBUG
#include <assert.h>
#endif

static void *allChunks[ 100000 ];
static int allocAt[ 100000 ];
static int nofChunks = 0;

#ifdef DEBUG
#define CALLOC(CNT,SIZE)	debugCalloc( (CNT), (SIZE), __LINE__ )
#define MALLOC(SIZE)	debugMalloc( (SIZE), __LINE__ )
#define FREE(WHAT)	debugFree( (WHAT) )
#else		/* DEBUG */
#define CALLOC(CNT,SIZE)	calloc( (CNT), (SIZE) )
#define MALLOC(SIZE)	malloc( (SIZE) )
#define FREE(WHAT)	free( (WHAT) )
#endif	/* DEBUG */

/* initial size of stretchable arrays */
#define INIT_ARR_SIZE 8
/* maximum number of different references in a substitute string;
 * one of them ("\0") is for the whole matched string */
#define MAX_DIFF_REFS 10

/* Secure `MALLOC'. */
#define SMALLOC(WHERE,CNT,TYPE)	\
	if( ! (WHERE = (TYPE*) MALLOC( (CNT) * sizeof( TYPE ) )) )	\
	{	\
		errno = ENOMEM;	\
		return (ERRET);	\
	}
/* Secure `CALLOC'. */
#define SCALLOC(WHERE,CNT,TYPE)	\
	if( ! (WHERE = (TYPE*) CALLOC( CNT, sizeof( TYPE ) )) )	\
	{	\
		errno = ENOMEM;	\
		return ERRET;	\
	}

static inline void* debugCalloc( size_t cnt, size_t size, int lineNo )
{
	allChunks[ nofChunks ] = calloc( cnt, size );
	allocAt[ nofChunks ] = lineNo;
	return allChunks[ nofChunks++ ];
}

static inline void* debugMalloc( size_t size, int lineNo )
{
	allChunks[ nofChunks ] = malloc( size );
	allocAt[ nofChunks ] = lineNo;
	return allChunks[ nofChunks++ ];
}

static inline void debugFree( void *where )
{
	int chunkIdx;
	
	for( chunkIdx = 0; chunkIdx < nofChunks; chunkIdx++ )
		if( allChunks[ chunkIdx ] == where )
			break;
#ifdef DEBUG
	assert( chunkIdx < nofChunks );
#endif
	for( ; chunkIdx < nofChunks - 1; chunkIdx++ )
	{
		allChunks[ chunkIdx ] = allChunks[ chunkIdx + 1 ];
		allocAt[ chunkIdx ] = allocAt[ chunkIdx + 1 ];
	}
	nofChunks--;

	free( where );
}

/* index proportional to size of the text */
typedef unsigned int t_idx;
/* equivalent of -1 for t_idx */
static t_idx negTIdx = (t_idx) -1;
/* index proportional to size of the regex */
typedef unsigned short r_idx;
/* equivalent of -1 for r_idx */
static r_idx negRIdx = (r_idx) -1;
/* index proportional to size of the history of repetitions */
typedef unsigned char h_idx;
/* equivalent of -1 for h_idx */
static h_idx negHIdx = (h_idx) -1;

/* tuple of text indices */
struct begend_s {
	t_idx begin;
	t_idx end;
};
typedef struct begend_s begend;

/* array of `begend's */
struct begendArr_s {
	begend *mbrs;
	size_t limit;
	size_t cap;
};
typedef struct begendArr_s begendArr;

/* flags modifying interpretation of regular expressions */
typedef unsigned char rxFlags;
/* whether substitutions shall be done globally (all possible disjunct) */
#define RF_GLOBAL		1
/* whether matching should be performed case-insensitively */
#define RF_ICASE		2
/* whether extended regular expressions shall be used instead of basic */
#define RF_BASIC		0
#define RF_EXTENDED	4
// /* whether Perl style regular expressions shall be used */
// #define RF_PERL			8
/* whether parentheses should be used for grouping only, not for reference in 
 * substituting */
#define RF_NOSUB		16

/* flags specifying the ordering of candidates */
typedef unsigned char rxCandOrdering;
/* By default, the candidates are sorted according to these criteria:
 * 		depth order (shallower is better),
 * 		left-right order (more to left is better),
 * 		greediness (greedy is better).	*/
#define RCO_DEFAULT	0
/* The direction of ordering (ascending vs. descending) can be switched using 
 * following flags (O = Order - nestedness, L = left-right order, 
 * G = greediness; the smaller value, the higher priority, if in ascending 
 * order) :	*/
#define RCO_O_ASC		0
#define RCO_O_DESC	32
#define RCO_L_ASC		0
#define RCO_L_DESC	64
#define RCO_G_ASC		128
#define RCO_G_DESC	0
/* This mask selects only the direction settings from `rxCandOrdering'. */
#define RCO_DIRMASK	224
/* The weights of ordering features (O/L/G) can be tuned using following 
 * switches (then they are weighted with decreasing weight with each next letter 
 * from the name of the flag; default is OLG) : */
#define RCO_OLG		0
#define RCO_OGL		1
#define RCO_LOG		2
#define RCO_LGO		3
#define RCO_GOL		4
#define RCO_GLO		5
/* This mask selects only the weights settings from `rxCandOrdering'. */
#define RCO_WMASK	7


/* type of the regular expression */
enum rxType_e { basic, extended };
typedef enum rxType_e rxType;

/* operators in the regex: concatenation, | (, & : only after implementing 
 * vim-style regexps), {.,.}, anchor, top node -- end of the regex */
enum operator_e { cat, or, /*and,*/ rep, anchor, top };
typedef enum operator_e operator;

/* mark of start of where a repeated subexpr. can be matched */
struct repMark_s {
	unsigned short* repCnt;					// array of counts of repetitions till here
																	// (sorted in ascending order)
																	// (all are permissible counts of rep.s for 
																	// the respective rep. op)
	struct repMark_s** repStart;		// array of respective marks for start of the first of reps
	_Bool unbounded;								// whether values in `repCnt' are merely lower bounds
	unsigned int nofMarks;					// size of both `repCnt' and `repStart'
	unsigned int nofLinks;					// number of links to this mark

	t_idx tIdx;											// index into text which this mark applies to
	h_idx repPrior;									// repetition this marks applies to
	t_idx start;										// start of candidates this marks applies to
};
typedef struct repMark_s repMark;

/* history element */
struct h_elm_s {
	unsigned int repCnt;		// count of repetitions
	_Bool unbounded;				// whether the repetition could be repeated unbounded
													// number of times
	t_idx start;						// text index of start of the last instantiation of this repetition
	repMark *mark;					// the associated repetition mark;
													// If no mark associated, `mark' == NULL.
	_Bool isOpen;						// whether this count may still change
	_Bool used;							// whether this repetition was used already
													// ...for example in "a+|b+" matched against in the 
													// text "bbb", the first rep. has always used == 0
};
typedef struct h_elm_s h_elm;

/* a candidate for a matching substring */
struct cand_s {
	t_idx start;						// start of the matching substring
	t_idx end;							// end of the matching substring
	h_elm *hist;						// history of repetitions
	begend *parens;					// history of matched parentheses
};
typedef struct cand_s cand;

/* array of candidates */
struct candArr_s {
	cand** mbrs;
	size_t cap;							// allocated size
	size_t limit;						// valid size
	_Bool isFree;						// whether candidates it holds are free,
													// i.e. out of the regex tree
													// TODO Remove if not proved necessary.
};
typedef struct candArr_s candArr;

/* An atom in the regex, i.e. a collection of letters that match.
 * The regex construct '.' has (ltrs == NULL && size == 0). */
struct atom_s {
	wchar_t *ltrs;					// the enumerated characters
	size_t size;						// number of elements in `ltrs'
	wctype_t *props;				// '[:property:]' constructs
// 	_Bool *propInverse;			// corresponding to the Perl '[:^...:]' construct
	size_t propsSize;				// number of elements in `props' and `propInverse'
	_Bool inverse;					// corresponding to the '[^...]' construct
};
typedef struct atom_s atom;

/* node in the syntactic regex parse tree */
struct node_s {
	operator op;
	h_idx lrOrder;						// left-right order within this type of nodes
														// for `op'==`rep' indexed 0..
														// for parentheses indexed 1..
  struct node_s *left, *right, *up;
														// left son, right son, father
	_Bool isRight;						// whether this node is the right son of its parent node
	struct node_s* adjoined;	// pointer to next point in regex to be analyzed together with this one
	struct node_s* startedRep;// the repetition operator whose repeated substring starts in this node
	struct node_s* parToOpen;	// the parenthesis to (recursively) open when this node is entered
														// If this node's `op' == rep, valid only for 
														// candidates who skipped the repetition.
	atom* atom;								// pointer to a single atom
	_Bool isStartNode;				// whether the start of the text matches with the point before this node
	_Bool isActive;						// whether this node shall be processed in this run yet
	_Bool isNActive;					// whether this node shall be processed with next input char
	r_idx depth;							// depth in the regex tree (the root has `depth' == 0)

	struct node_s* nextAct;		// link to the next active node
	struct node_s* nextNAct;	// link to the next node to become active with the next input char

	t_idx lastTIdx;						// last text index when this node was visited (and updated)

														// Candidates in following arrays are sorted in 
														// ascending order with respect to their `start'.
	candArr lCands;						// set of candidates from the left son
	candArr nextLCands;				// set of candidates from the left son that used the input char already
	candArr rCands;						// set of candidates from the right son
	candArr nextRCands;				// set of candidates from the right son that used the input char already
};
typedef struct node_s node;

/* properties of a repetition operator */
struct repProp_s {
	unsigned int minReps, maxReps;	// 0 in maxReps means unbounded
	struct node_s* firstRepd;				// first node of the repeated subexpression (for rep. ops only)
	struct node_s* enclRep;					// the most tightly enclosing repetition operator
	h_idx firstEnRep;								// LR-index of the first rep. op enclosed in this one (or index
																	// of this rep. op if no other is enclosed)
	_Bool isGreedy;									// whether this is a greedy operator
	unsigned char order;						// depth order (nestedness) with respect to repetition constructs
	r_idx lrOrder;									// left-right order in the regex with respect to repetition constructs
																	// ('and' operators use this field, too)
};
typedef struct repProp_s repProp;

/* annotated property of a repetition operator - used only for sorting during 
 * compiling the regex */
struct annRepProp_s {
	unsigned char oMagn, lMagn, gMagn;	// magnitudes (importance) of O/L/G
	_Bool oDir, lDir, gDir;							// whether the ordering is ascending with respect to O/L/G
	repProp val;												// the associated repetition operator's properties
};
typedef struct annRepProp_s annRepProp;

/* linked list of `t_idx's */
struct t_idx_l_s {
	t_idx val;
	struct t_idx_l_s *prev, *next;
};
typedef struct t_idx_l_s t_idx_l;

/* member of a linked list of repetition marks */
struct repMark_l_s {
	repMark *val;
	struct repMark_l_s *next;
};
typedef struct repMark_l_s repMark_l;

/* direction of moving within the binary parse tree */
enum dir_e { left, right, up };
typedef enum dir_e dir;

/* member of a linked list of candidates */
struct cand_l_s {
	cand *val;
	struct cand_l_s *next;
};
typedef struct cand_l_s cand_l;

/* collection of candidates starting at the same place */
struct candsCluster_s {
	unsigned int nofCandsInTree;	// how many candidates with this start are somewhere
																// in the regex tree yet
	cand_l *matchingCands;				// candidates with this start that match the regex
																// (in ascending order with respect to the end 
																// of matching substring)
};
typedef struct candsCluster_s candsCluster;

/* resources bound with analyzing a text using a regular expression */
struct rxResources_s {
	node *allocNodes;					// preallocated nodes
	r_idx nofNodes;						// number of nodes in `allocNodes'
	atom *allocAtoms;					// preallocated atoms
	wchar_t *allocLtrs;				// preallocated letters
	wchar_t *allocProps;			// preallocated properties (character classes)

	node *tree;								// the regex's parse tree
	node *firstStartNode;
	r_idx depth;							// depth of the parse tree
	node **actNodes;					// currently active nodes (to be processed)
	node **nextActNodes;			// active nodes for the next input char

	repProp *repProps;				// properties of repetition operators
														// (sorted with respect to the priority)
	h_idx *repPriors;					// priorities of repetition operators
														// (sorted with respect to the LR-order)
	r_idx nofReps;						// total number of repetition operators

	begend *initParens;				// initial parentheses matching for a new candidate
	r_idx nofParens;					// number of pairs of parentheses in use

	wchar_t *text;						// the text, null-delimited
	t_idx textLen;						// length of the text
	t_idx nextTIdx;						// next index into the text to process
	void **marksTree;					// data structure (tree) containing repetition marks
	_Bool isClean;						// whether the rx. tree has no candidates in it
														// (`marksTree' == `text' == NULL &&
														//  `textLen' == `nextTIdx' == 0)
	candsCluster *bestCands;	// array of best candidates, indexed by their starts
	t_idx firstStart;					// first start index of a matching candidate
														// (i.e. first index into `bestCands', where 
														// `matchingCands' != NULL might hold)
	begend lastMatcher;				// the end of the last found matcher
};
typedef struct rxResources_s rxAnaRess;

/* exported functions */
rxAnaRess *rxCompile( const wchar_t *const regex, rxFlags flags, rxCandOrdering rco );
inline _Bool cleanRress( rxAnaRess *rress );
inline _Bool freeRress( rxAnaRess *rress );

int matches( const wchar_t *const text, const wchar_t *const regex,
										 rxFlags flags );
int matchesPrec( const wchar_t *const text, rxAnaRess *const rress );
begend firstMatch( const wchar_t *const text, rxAnaRess *const rress );
begend nextMatch( rxAnaRess *const rress );

begend nextDisjunctMatch( rxAnaRess *const rress );
begendArr allMatches( const wchar_t *const text, const wchar_t *const regex,
											rxFlags flags, rxCandOrdering rco );
begendArr allMatchesPrec( const wchar_t *const text, rxAnaRess *const rress );
begendArr allDisjunctMatches( const wchar_t *const text, const wchar_t *const regex,
															rxFlags flags, rxCandOrdering rco );
begendArr allDisjunctMatchesPrec( const wchar_t *const text, rxAnaRess *const rress );
wchar_t *substitute( const wchar_t *text,
										 const wchar_t *regex,
										 const wchar_t *subst,
										 const rxFlags flags,
										 const rxCandOrdering rco );
// _Bool isRegex( const wchar_t *regex );

/* exported constants */
const begend invBegend = { 1, 0 };
const begend excBegend = { 2, 0 };
const begendArr excBegendArr = { 0x0, 1, 0 };

/* auxilliary functions */
static inline void assignText( const wchar_t *const text, rxAnaRess *const rress );
static inline unsigned char countSubChunks(
			wchar_t *subst, size_t subLen, r_idx nofParens, _Bool *usesRefs );
static inline _Bool mergeToBest( candArr *matching, rxAnaRess *const rress );
static inline cand * nextCand( rxAnaRess *const rress );
static inline cand *nextDisjunctCand( rxAnaRess *const rress );
static inline candArr allDisjunctCandsPrec( const wchar_t *const text, rxAnaRess 
																						*const rress );
static candArr processChar( rxAnaRess *const rress );
static inline void detach( candArr *cArr, rxAnaRess *rress );
static inline void updNode( node* node, t_idx tIdx );
static inline _Bool sendUp( node *curNode, candArr *inCArr,
										r_idx curDepth, r_idx *newDepth, rxAnaRess *rress );
static inline _Bool sendUpToNext( node *curNode, candArr *inCArr,
										r_idx curDepth, r_idx *newDepth, rxAnaRess *rress );
static inline candArr cloneCArr( candArr inCArr, rxAnaRess *rress );
static inline void openParens( const candArr cands, const node *parToOpen,
															 const t_idx where, const rxAnaRess *const rress );
static inline _Bool openReps( const candArr cands, const node *encNode,
															const t_idx startIdx, rxAnaRess *const rress );
static inline candArr mergeCands( candArr* arr1, candArr* arr2, rxAnaRess *rress );
static inline _Bool disposeCand( cand *cand, rxAnaRess *rress );
static inline void disposeFreeCand( cand *cand, rxAnaRess *rress );
static inline _Bool disposeCands( candArr *cands, rxAnaRess *rress );
static inline _Bool disposeEarlyCands( const t_idx maxStart, rxAnaRess *const rress );
static inline _Bool disposeEarlyCandsSub( const t_idx maxStart, candArr *const cArr,
																					rxAnaRess *const rress );
static inline _Bool disposeTR( cand* referee, h_idx repPrior, rxAnaRess *rress );
static inline unsigned int getBestRepCnt( repMark *mark,
			unsigned int minReps, unsigned int maxReps, _Bool isGreedy );
static inline repMark *addRepMark( t_idx tIdx, h_idx repPrior, t_idx start,
			t_idx prevTIdx, h_idx prevRepPrior, rxAnaRess *rress );
static inline _Bool isInvCArr( candArr cArr );
static int compMarkKeys( const void *a, const void *b );
static int compRepProps( const void *a, const void *b );
static inline int compCands( const cand *const cand1, const cand *const cand2,
														 const rxAnaRess *const rress );
static repMark *dumpMarksTree( void **marksTree );
static signed char checkNofLinks( rxAnaRess *rress );
static inline unsigned char parseOctal( wchar_t a, wchar_t b, wchar_t c );
static inline unsigned char parseHexa( wchar_t a, wchar_t b );
static inline unsigned int parseUInt( const wchar_t* str, r_idx *pos );
static inline _Bool isOpeningPar( node* node );
static inline _Bool isDot( node* node );

/* auxilliary constants */
static const candArr excCArr = { NULL, 0, 1 };
static const cand invCand = { 1, 0, 0x0, 0x0 };
static cand invCand_nonconst = { 1, 0, 0x0, 0x0 };
static cand *invCandP = &invCand_nonconst;
static const cand excCand = { 2, 0, 0x0, 0x0 };
static cand excCand_nonconst = { 2, 0, 0x0, 0x0 };
static cand *excCandP = &excCand_nonconst;

/* auxilliary variables for testing purposes */
static repMark *dumpedRM;
static int drmIdx;
static size_t drmSize;

/**
 * Returns 1 or 0 depending on whether `text' matches the regular expression 
 * `regex'. Returns -1 in case of exception.
 *
 * Arguments:
 * 	text  : text to be matched
 * 	regex : the regular expression to be used for matching
 * 	flags	: flags modifying interpretation of `regex'
 *
 * Returns:
 * 	1		... if the text matched the regex
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET -1
int matches( const wchar_t *const text, const wchar_t *const regex,
										 rxFlags flags )
{
	signed char retVal;

	if( wcslen( regex ) == 0 )
		return 1;
	// TODO Check special cases

	rxAnaRess *rress;
	if( ! (rress = rxCompile( regex, flags, RCO_DEFAULT )) )
		return ERRET;

	if( ( -1 == (retVal = matchesPrec( text, rress )) ) ||
			( ! freeRress( rress ) ) )
		return ERRET;

#ifdef DEBUG
	assert( nofChunks == 0 );
#endif
	return retVal;
}

/**
 * Returns 1 or 0, depending on whether `text' matches the precompiled regular 
 * expression described by `rress'. Returns -1 in case of exception.
 *
 * Arguments:
 * 	text  : text to be matched
 * 	rress : the precompiled regular expression to be used for matching
 * 					It should be clean (not used by other functions than `matches'). In 
 * 					any case, it is cleaned before being returned.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET -1
int matchesPrec( const wchar_t *const text, rxAnaRess *const rress )
{
#define RETURN(RETVAL) \
	if( ! cleanRress( rress ) )	\
		return ERRET;	\
	return (RETVAL);

	if( !rress->isClean )
	{
		if( ! cleanRress( rress ) )
			return ERRET;
	}

	rress->text = text;
	rress->textLen = wcslen( text );
	rress->isClean = 0;
	candArr matchingCArr;
	
	for( rress->nextTIdx = 0; rress->nextTIdx <= rress->textLen; rress->nextTIdx++ )
	{
#ifdef DEBUG
		assert( 1 == checkNofLinks( rress ) );
#endif

		// If some candidates are found,
		if( ( matchingCArr = processChar( rress ) ).limit )
		{
			if( isInvCArr( matchingCArr ) )
			{
				// Throw an exception.
				return ERRET;
			}
			else
			{
				if( ! (disposeCands( &matchingCArr, rress )) )
					return ERRET;

				RETURN(1);
			}
		}
		else if( matchingCArr.cap )
			FREE( matchingCArr.mbrs );
	}
	RETURN(0);
}

/**
 * Finds the first substring in given text matching the given regex. First means 
 * with the lowest index of the last matched character, and within matching 
 * substrings with the same index of the last character, the one with the lowest 
 * index of the first character.
 *
 * Arguments:
 * 	text	: text to be matched
 * 	rress	: precompiled regular expression to match against
 *
 * Returns either the appropriate data in the structure `begend' if a match was 
 * found, or the constant `begend invBegend' (which has `begin' > `end') if 
 * `text' does not match `regex'.
 * 	As a side effect, the current state of analysis of `text' is saved in 
 * `rress'.
 *
 * If an exception occurs, `excBegend' is returned.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET excBegend
begend firstMatch( const wchar_t *const text, rxAnaRess *const rress )
{
	// Ensure `rress' is clean.
	if( !rress->isClean )
	{
		if( ! cleanRress( rress ) )
			return ERRET;
	}
	// Assign the text to `rress'.
	assignText( text, rress );
	// Find the match.
	return nextMatch( rress );
}

/**
 * Assigns the text to the regex resources.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET /**/
static inline void assignText( const wchar_t *const text, rxAnaRess *const rress )
{
	rress->text = text;
	rress->textLen = wcslen( text );
	rress->firstStart = rress->nextTIdx = 0;
	SCALLOC( rress->bestCands, wcslen( text ) + 1, candsCluster )
	rress->isClean = 0;
	rress->lastMatcher.begin = rress->lastMatcher.end = negTIdx;
}

/**
 * Finds the next substring in given text matching the given regex. The ordering 
 * of matching substrings is the same as in `firstMatch'. Next means next from 
 * that returned by the last call to either `firstMatch' or `nextMatch' or 
 * `nextDisjunctMatch'.
 *
 * Arguments:
 * 	rress	: precompiled regular expression to match against
 *
 * Returns either the appropriate data in the structure `begend' if a match was 
 * found, or the constant `begend invBegend' (which has `begin' > `end') if 
 * `text' does not match `regex'.
 * 	As a side effect, the current state of analysis of `text' is saved in 
 * `rress'.
 *
 * If an exception occurs, `excBegend' is returned.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET excBegend
begend nextMatch( rxAnaRess *const rress )
{
	cand *matcher = nextCand( rress );
	if( matcher->start == excCand.start &&
			matcher->end   == excCand.end )
	{
		return ERRET;
	}
	if( matcher->start == invCand.start &&
			matcher->end   == invCand.end )
	{
		return invBegend;
	}
	
	begend be;
	be.begin = matcher->start;
	be.end   = matcher->end;
	disposeFreeCand( matcher, rress );
	return be;
}

/**
 * Implements `nextMatch', but in contrast to that function, returns the whole 
 * candidate, instead of only its begin and end indices.
 *
 * In case of exception, returns `excCandP'.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET excCandP
static inline cand * nextCand( rxAnaRess *const rress )
{
	cand_l *matcher_elm;
	cand *matcher;

	// Check candidates found by previous runs first.
	while( rress->firstStart < rress->nextTIdx )
	{
		// If the set of candidates is not definite yet, proceed to analyzing.
		if( rress->bestCands[ rress->firstStart ].nofCandsInTree )
			break;
		// If the set of candidates is definite and non-empty,
		else if( (matcher_elm = rress->bestCands[ rress->firstStart ].matchingCands) )
		{
			matcher = matcher_elm->val;
			rress->lastMatcher.begin = matcher->start;
			rress->lastMatcher.end = matcher->end;
			rress->bestCands[ rress->firstStart ].matchingCands = matcher_elm->next;
			FREE( matcher_elm );
			return matcher;

		}
		rress->firstStart++;
	}

	// Find new candidates then.
	candArr matchingCArr;
	for( ; rress->nextTIdx <= rress->textLen; rress->nextTIdx++ )
	{
#ifdef DEBUG
		assert( 1 == checkNofLinks( rress ) );
#endif

		// If some candidates are found,
		if( ( matchingCArr = processChar( rress ) ).limit )
		{
			// If an exception occured,
			if( isInvCArr( matchingCArr ) )
			{
				// Throw the exception.
				cleanRress( rress );
				return ERRET;
			}
			// If valid candidates were found,
			else
			{
				// Merge new candidates to lists of best candidates.
				if( ! mergeToBest( &matchingCArr, rress ) )
					return ERRET;
			}
		}
		else if( matchingCArr.cap )
			FREE( matchingCArr.mbrs );

		// Find whether the next candidate is known now.
		while( rress->firstStart <= rress->nextTIdx )
		{
			// If the set of candidates is not definite yet, continue with analyzing.
			if( rress->bestCands[ rress->firstStart ].nofCandsInTree &&
						rress->nextTIdx != rress->textLen )
				break;
			// If the set of candidates is definite and non-empty,
			else if( (matcher_elm = rress->bestCands[ rress->firstStart ].matchingCands) )
			{
				matcher = matcher_elm->val;
				rress->lastMatcher.begin = matcher->start;
				rress->lastMatcher.end = matcher->end;
				rress->bestCands[ rress->firstStart ].matchingCands = matcher_elm->next;
				FREE( matcher_elm );
				// Move to the next input character and return.
				rress->nextTIdx++;
				return matcher;

			}
			rress->firstStart++;
		}
	}

	rress->lastMatcher.begin = rress->lastMatcher.end = rress->textLen;
	return invCandP;
}

/**
 * Finds the next substring in given text matching the given regex, disjunct 
 * with last such substring found.  The ordering of matching substrings is the 
 * same as in `firstMatch'.  "Last found" means next from that returned by the 
 * last call to either `firstMatch' or `nextMatch' or `nextDisjunctMatch'.
 *
 * Arguments:
 * 	rress	: precompiled regular expression to match against
 *
 * Returns either the appropriate data in the structure `begend' if a match was 
 * found, or the constant `begend invBegend' (which has `begin' > `end') if 
 * `text' does not match `regex'.
 * 	As a side effect, the current state of analysis of `text' is saved in 
 * `rress'.
 *
 * If an exception occurs, `excBegend' is returned.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET excBegend
begend nextDisjunctMatch( rxAnaRess *const rress )
{
	cand *matcher = nextDisjunctCand( rress );
	if( matcher->start == excCand.start &&
			matcher->end   == excCand.end )
		return ERRET;

	if( matcher->start == invCand.start &&
			matcher->end   == invCand.end )
		return invBegend;

	disposeFreeCand( matcher, rress );
	return rress->lastMatcher;
}

/**
 * Implements `nextDisjunctMatch', but in contrast to that function, returns the 
 * whole candidate, instead of only its begin and end indices.
 *
 * If there is no next disjunct candidate, returns `invCand'. In case of 
 * exception, returns `excCand'.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET excCandP
static inline cand *nextDisjunctCand( rxAnaRess *const rress )
{
	cand_l *matcher_elm;
	cand *matcher;

	// Dispose candidates that would not be disjunct.
	if( rress->lastMatcher.end != negTIdx &&
			! disposeEarlyCands(
								rress->lastMatcher.end -
					(rress->lastMatcher.begin != rress->lastMatcher.end),
					rress ) )
		return ERRET;

	// Check candidates found by previous runs first.
	while( rress->firstStart < rress->nextTIdx )
	{
		// If the set of candidates is not definite yet, proceed to analyzing.
		if( rress->bestCands[ rress->firstStart ].nofCandsInTree )
			break;
		// If the set of candidates is definite and non-empty,
		else if( (matcher_elm = rress->bestCands[ rress->firstStart ].matchingCands) )
		{
			matcher = matcher_elm->val;
			rress->lastMatcher.begin = matcher->start;
			rress->lastMatcher.end = matcher->end;
			rress->bestCands[ rress->firstStart ].matchingCands = matcher_elm->next;
			FREE( matcher_elm );
			return matcher;

		}
		rress->firstStart++;
	}

	// Find new candidates then.
	candArr matchingCArr;
	for( ; rress->nextTIdx <= rress->textLen; rress->nextTIdx++ )
	{
#ifdef DEBUG
		assert( 1 == checkNofLinks( rress ) );
#endif

		// If some candidates are found,
		if( ( matchingCArr = processChar( rress ) ).limit )
		{
			// If an exception occured,
			if( isInvCArr( matchingCArr ) )
			{
				// Throw the exception.
				cleanRress( rress );
				return ERRET;
			}
			// If valid candidates were found,
			else
			{
				// Merge new candidates to lists of best candidates.
				if( ! mergeToBest( &matchingCArr, rress ) )
					return ERRET;
			}
		}
		else if( matchingCArr.cap )
			FREE( matchingCArr.mbrs );

		// Find whether the next candidate is known now.
		while( rress->firstStart <= rress->nextTIdx )
		{
			// If the set of candidates is not definite yet, continue with analyzing.
			if( rress->bestCands[ rress->firstStart ].nofCandsInTree &&
						rress->nextTIdx != rress->textLen )
				break;
			// If the set of candidates is definite and non-empty,
			else if( (matcher_elm = rress->bestCands[ rress->firstStart ].matchingCands) )
			{
				matcher = matcher_elm->val;
				rress->lastMatcher.begin = matcher->start;
				rress->lastMatcher.end = matcher->end;
				rress->bestCands[ rress->firstStart ].matchingCands = matcher_elm->next;
				// Move to the next input character and return.
				rress->nextTIdx++;
				FREE( matcher_elm );
				return matcher;

			}
			rress->firstStart++;
		}
	}

	rress->lastMatcher.begin = rress->lastMatcher.end = rress->textLen;
	return invCandP;
}

/**
 * Finds all substrings in the given text matching the given regex. The ordering 
 * of matching substrings is the same as in `firstMatch'.
 *
 * Arguments:
 * 	text	: the text to be matched
 * 	regex	: the regular expression to match `text' against
 * 	flags	: flags modifying interpretation of `regex'
 * 	rco		: flags specifying the ordering of candidates
 *
 * Returns an array `begendArr', a structure containing a pointer to start of 
 * the array and number of its elements.
 *
 * If an exception occurs, `excBegendArr' is returned.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET excBegendArr
begendArr allMatches( const wchar_t *const text, const wchar_t *const regex,
											rxFlags flags, rxCandOrdering rco )
{
	rxAnaRess *rress;
	if( ! (rress = rxCompile( regex, flags, rco )) )
		return ERRET;
	begendArr retVal = allMatchesPrec( text, rress );
	freeRress( rress );
	return retVal;
}

/**
 * Finds all substrings in the given text matching the given precompiled regular 
 * expression. The ordering of matching substrings is the same as in 
 * `firstMatch'.
 *
 * Arguments:
 * 	text	: the text to be matched
 * 	rress	: precompiled regular expression to match against
 *
 * Returns an array `begendArr', a structure containing a pointer to start of 
 * the array and number of its elements. The `rress' is not freed nor cleaned 
 * after call to this function.
 *
 * If an exception occurs, excBegendArr is returned.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET excBegendArr
begendArr allMatchesPrec( const wchar_t *const text, rxAnaRess *const rress )
{
	// Ensure `rress' is clean.
	if( !rress->isClean )
	{
		if( ! cleanRress( rress ) )
			return ERRET;
	}
	// Assign the text to `rress'.
	assignText( text, rress );
	// Find all matches.
	begendArr retVal;
	if( ! (retVal.mbrs = (begend*) malloc( (retVal.cap = INIT_ARR_SIZE) * sizeof( begend ) )) )
	{
		retVal.cap = 0;
		errno = ENOMEM;
		return ERRET;
	}
	retVal.limit = 0;
	begend newMatch;
	while( 1 )
	{
		// Get the next match.
		newMatch = nextMatch( rress );
		// If an exception occured,
		if( newMatch.begin == excBegend.begin && newMatch.end == excBegend.end )
		{
			free( retVal.mbrs );
			return ERRET;
		}
		// If there are no more matches,
		else if( newMatch.begin == invBegend.begin && newMatch.end == invBegend.end )
		{
			return retVal;
		}
		// So, there is a new match.
		// If there is no free place in `retVal.mbrs',
		if( retVal.limit >= retVal.cap )
		{
			// Stretch `retVal.mbrs'.
			if( !( retVal.mbrs =
							(begend*) realloc( retVal.mbrs,
											(retVal.cap += retVal.cap) * sizeof( begend ) )
					) )
			{
				// If an exception occurs,
				errno = ENOMEM;
				return ERRET;
			}
		}
		// Save the newly found match.
		retVal.mbrs[ retVal.limit++ ] = newMatch;
	}
}

/**
 * Finds all subsequent disjunct substrings in the given text matching the given 
 * regex.  The ordering of matching substrings is the same as in `firstMatch'.
 *
 * Arguments:
 * 	text	: the text to be matched
 * 	regex	: the regular expression to match `text' against
 * 	flags	: flags modifying interpretation of `regex'
 * 	rco		: flags specifying the ordering of candidates
 *
 * Returns an array `begendArr', a structure containing a pointer to start of 
 * the array and number of its elements.
 *
 * If an exception occurs, `excBegendArr' is returned.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET excBegendArr
begendArr allDisjunctMatches( const wchar_t *const text, const wchar_t *const regex,
															rxFlags flags, rxCandOrdering rco )
{
	rxAnaRess *rress;
	if( ! (rress = rxCompile( regex, flags, rco )) )
		return ERRET;
	begendArr retVal = allDisjunctMatchesPrec( text, rress );
	freeRress( rress );
	return retVal;
}

/**
 * Finds all subsequent disjunct substrings in the given text matching the given 
 * precompiled regular expression. The ordering of matching substrings is the 
 * same as in `firstMatch'.
 *
 * Arguments:
 * 	text	: the text to be matched
 * 	rress	: precompiled regular expression to match against
 *
 * Returns an array `begendArr', a structure containing a pointer to start of 
 * the array and number of its elements. The `rress' is not freed nor cleaned 
 * after call to this function.
 *
 * If an exception occurs, excBegendArr is returned.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET excBegendArr
begendArr allDisjunctMatchesPrec( const wchar_t *const text, rxAnaRess *const rress )
{
	candArr retCands = allDisjunctCandsPrec( text, rress );
	// Check for exception.
	if( retCands.limit == excCArr.limit &&
			retCands.cap   == excCArr.cap )
		return ERRET;

	unsigned int candIdx;
#define FREEMEM	\
	for( candIdx = retCands.limit - 1; \
						candIdx != (unsigned int) -1; \
						candIdx-- ) \
		disposeFreeCand( retCands.mbrs[ candIdx ], rress ); \
	free( retCands.mbrs )
	
	// Transform candidates to only their begends.
	begend be;
	begendArr retBes;
	if( ! (retBes.mbrs = (begend*) malloc(
						(retBes.cap = retCands.limit) * sizeof( begend ) )) )
	{
		FREEMEM;
		return ERRET;
	}
	for( candIdx = (retBes.limit = retCands.limit) - 1;
						candIdx != (unsigned int) -1;
						candIdx-- )
	{
		retBes.mbrs[ candIdx ].begin = retCands.mbrs[ candIdx ]->start;
		retBes.mbrs[ candIdx ].end   = retCands.mbrs[ candIdx ]->end;
	}
	FREEMEM;
	return retBes;
}

/**
 * Implements `allDisjunctMatchesPrec', but in contrast to that function, 
 * returns the whole candidate, instead of only its begin and end indices.
 *
 * In case of exception, returns `excCand'.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET excCArr
static inline candArr allDisjunctCandsPrec( const wchar_t *const text, rxAnaRess *const rress )
{
	// Ensure `rress' is clean.
	if( !rress->isClean )
	{
		if( ! cleanRress( rress ) )
			return ERRET;
	}
	// Assign the text to `rress'.
	assignText( text, rress );
	// Find all matches.
	candArr retVal;
	if( ! (retVal.mbrs = (cand**) malloc( (retVal.cap = INIT_ARR_SIZE) * sizeof( cand* ) )) )
	{
		retVal.cap = 0;
		errno = ENOMEM;
		return ERRET;
	}
	retVal.limit = 0;
	cand *newMatch;
	while( 1 )
	{
		// Get the next match.
		newMatch = nextDisjunctCand( rress );
		// If an exception occured,
		if( newMatch->start == excCand.start &&
				newMatch->end   == excCand.end )
		{
			free( retVal.mbrs );
			return ERRET;
		}
		// If there are no more matches,
		else if( newMatch->start == invCand.start &&
						 newMatch->end   == invCand.end )
		{
			return retVal;
		}
		// So, there is a new match.
		// If there is no free place in `retVal.mbrs',
		if( retVal.limit >= retVal.cap )
		{
			// Stretch `retVal.mbrs'.
			if( !( retVal.mbrs =
							(cand**) realloc( retVal.mbrs,
											(retVal.cap += retVal.cap) * sizeof( cand* ) )
					) )
			{
				// If an exception occurs,
				errno = ENOMEM;
				return ERRET;
			}
		}
		// Save the newly found match.
		retVal.mbrs[ retVal.limit++ ] = newMatch;
	}
}

/**
 * Substitutes disjunct subsequent occurrences of substrings matching given 
 * regular expression in a text by given substitute string. Substitute flags 
 * have to be supplied explicitly.
 *
 * Arguments:
 * 	text	: the text to be matched
 * 	regex	: the regular expression to match agains
 * 	subst	: the string to substitute for matching substrings
 * 	flags	: flags modifying interpretation of `regex' and the substitution
 * 	rco		: flags specifying the ordering of candidates
 *
 * Returns the text after substituting matching substrings for the substitute 
 * string.
 *
 * If an exception occurs, NULL is returned.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET NULL
wchar_t *substitute( const wchar_t *text,
										 const wchar_t *regex,
										 const wchar_t *subst,
										 const rxFlags flags,
										 const rxCandOrdering rco )
{
	wchar_t *ret;
	size_t inLen = wcslen( text );
	size_t subLen;

#ifdef RETURN
#undef RETURN
#endif

#ifdef DEBUG
  int origNofChunks = nofChunks;
#define RETURN( RETVAL )	\
	FREEMEM;	\
	assert( nofChunks == origNofChunks );	\
	return RETVAL;
#else
#define RETURN( RETVAL )	\
	FREEMEM;	\
	return RETVAL;
#endif

#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM /**/
	// If all occurrences shall be substituted,
	if( flags & RF_GLOBAL )
	{
		rxAnaRess *rress;
		if( ! (rress = rxCompile( regex, flags, rco )) )
		{
			RETURN( ERRET );
		}

		candArr mCands = allDisjunctCandsPrec( text, rress );

		unsigned int candIdx;
#define FREEMCANDS	\
	for( candIdx = mCands.limit - 1; \
						candIdx != (unsigned int) -1; \
						candIdx-- ) \
		disposeFreeCand( mCands.mbrs[ candIdx ], rress ); \
	free( mCands.mbrs )
#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM freeRress( rress ); FREEMCANDS
	
		// If an exception occured,
		if( mCands.limit == excCArr.limit &&
				mCands.cap   == excCArr.cap )
		{
			RETURN( ERRET );
		}
		// If there is no matcher,
		if( ! mCands.limit )
		{
			// Return a copy of the input string.
			if( !( ret = (wchar_t*) malloc( (inLen + 1) * sizeof( wchar_t ) ) ) )
			{
				errno = ENOMEM;
				RETURN( ERRET );
			}
			RETURN( wmemcpy( ret, text, inLen + 1 ) );
		}
		// If there are some matchers,
		{
			// Find whether references are in use.
				// References may be disabled.
			_Bool usesRefs = !( flags & RF_NOSUB );

			subLen = wcslen( subst );
			unsigned char nofSubChunks = 0;

				// Count number of references in the substitute string.
			if( usesRefs && subLen )
				nofSubChunks = countSubChunks( subst, subLen,
																			 rress->nofParens, &usesRefs );
			else
				usesRefs = 0;

			/* total length of substrings to be substituted (deleted) */
			size_t outLen = inLen, copiedLen;
			unsigned int mIdx;
			cand *mCand;
				// Subtract total length of deleted substrings.
			for( mCand = mCands.mbrs[ mIdx = 0 ];
						mIdx < mCands.limit;
						mCand = mCands.mbrs[ ++mIdx ] )
			{
				outLen -= mCand->end - mCand->start;
			}

			t_idx inTIdx, outTIdx;
			// If the substitute string is verbatim,
			if( !usesRefs )
			{
				// Return the input string with the matchers substituted.
					// Add total length of inserted substrings.
				outLen += mCands.limit * subLen;

				if( !( ret = (wchar_t*) malloc(
									( outLen + 1 ) * sizeof( wchar_t ) ) ) )
				{
					errno = ENOMEM;
					RETURN( ERRET );
				}
					// Substitute the deleted substrings.
				outTIdx = 0, inTIdx = 0;
				for( mIdx = 0; mIdx < mCands.limit; mIdx++ )
				{
					mCand = mCands.mbrs[ mIdx ];
					// Copy the foregoing, not-deleted substring.
					if( (copiedLen = mCand->start - inTIdx) )
					{
						wmemcpy( ret + outTIdx, text + inTIdx, copiedLen );
						outTIdx += copiedLen;
						inTIdx += copiedLen;
					}
					// Copy the substitute string in place of the deleted substring.
					if( subLen )
					{
						wmemcpy( ret + outTIdx, subst, subLen );
						outTIdx += subLen;
					}
					inTIdx += mCand->end - mCand->start;
				}
				// Copy the last, not-deleted substring.
				wmemcpy( ret + outTIdx, text + inTIdx, inLen + 1 - inTIdx );

				RETURN( ret );
			}	// if( !usesRefs )
			else
			{
				// The substitute string needs to be broken into several substitute 
				// substrings, either verbatim, or references.

				/* pointers to subsequent chunks of the substitute string: 
				 * verbatim-reference-verbatim-... */
				wchar_t **subChunks;
				// The last member of `subChunks' will be pointer after the last char of 
				// `subst'.
				SMALLOC( subChunks, nofSubChunks + 1, wchar_t* )
				/* whether each of the chunks is verbatim (as opposed to a reference) */
				_Bool *isVerbatim;
				SMALLOC( isVerbatim, nofSubChunks, _Bool )
				/* the substitute string unescaped */
				wchar_t *unescaped;
				SMALLOC( unescaped, subLen + 1, wchar_t )
				unsigned int unIdx, unLen;
#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM freeRress( rress ); FREE( subChunks ); \
								FREE( unescaped ); FREE( isVerbatim ); FREEMCANDS

				/* number how many times particular references will be used */
				unsigned int nofUses[ 1 + rress->nofParens ];
				memset( nofUses, 0, ( 1 + rress->nofParens ) * sizeof( unsigned int ) );

				// Count necessary size of the return string.
				// Create the unescaped substitute string.
				_Bool lastVerbatim = 0;
				t_idx subIdx;
				unsigned int subChunkIdx = 0;
				unIdx = 0;
				size_t verbaLen = 0;
					// Count numbers of different references,
				for( subIdx = 0; subIdx < subLen; subIdx++ )
				{
					if( subst[ subIdx ] == L'\\' )
					{
						// Read in the next char.
						// If a reference follows,
						if( L'0' <= subst[ ++subIdx ] &&
							subst[ subIdx ] <= (wchar_t) ( L'0' + rress->nofParens ) )
						{
							nofUses[ (wint_t) ( subst[ subIdx ] - L'0' ) ]++;
							subChunks[ subChunkIdx ] = unescaped + unIdx;
							unescaped[ unIdx++ ] = subst[ subIdx ];
								// Add the needed space for the last verbatim substitute substring.
							if( lastVerbatim && subChunkIdx )
								verbaLen += subChunks[ subChunkIdx ] - subChunks[ subChunkIdx - 1 ];
							lastVerbatim = isVerbatim[ subChunkIdx++ ] = 0;
						}
						else if( ! lastVerbatim )
						{
							subChunks[ subChunkIdx ] = unescaped + unIdx;
							lastVerbatim = isVerbatim[ subChunkIdx++ ] = 1;
							// Either the backslash served as an escape character:
								// If there exists a character after the backslash,
							if( subIdx < subLen )
								unescaped[ unIdx++ ] = subst[ subIdx ];
							// Or it was a literal backslash.
							else
								unescaped[ unIdx++ ] = subst[ subIdx - 1 ];
						}
					}
					// If verbatim string follows,
					else
					{
						// If it starts here,
						if( ! lastVerbatim )
						{
							subChunks[ subChunkIdx ] = unescaped + unIdx;
							lastVerbatim = isVerbatim[ subChunkIdx++ ] = 1;
						}
						unescaped[ unIdx++ ] = subst[ subIdx ];
					}
				}
				unescaped[ (unLen = unIdx) ] = L'\0';
				subChunks[ nofSubChunks ] = unescaped + unLen;
					// Add the needed space for the last verbatim substitute substring.
				if( lastVerbatim && subChunkIdx )
					verbaLen += subChunks[ subChunkIdx ] - subChunks[ subChunkIdx - 1 ];

				outLen += mCands.limit * verbaLen;

						// Add the needed space for referenced matched substrings.
				begend be;
				unsigned int refIdx;
				for( mCand = mCands.mbrs[ mIdx = 0 ];
									mIdx < mCands.limit;
									mCand = mCands.mbrs[ ++mIdx ] )
				{
						// for the reference "\0":
					outLen += ( mCand->end - mCand->start ) * nofUses[ 0 ];
						// for all other references:
					for( refIdx = 1; refIdx <= rress->nofParens; refIdx++ )
					{
							// Add the parenthesized spans that were not skipped.
						be = mCand->parens[ refIdx - 1 ];
						outLen += (be.end > be.begin) ?
									( be.end - be.begin ) * nofUses[ refIdx ] : 0;
					}
				}

				if( !( ret = (wchar_t*) malloc(
									( outLen + 1 ) * sizeof( wchar_t ) ) ) )
				{
					errno = ENOMEM;
					RETURN( ERRET );
				}

				// Perform the substitution.
				outTIdx = 0, inTIdx = 0;
				int subPartLen;
					// For each of the matchers,
				for( mIdx = 0; mIdx < mCands.limit; mIdx++ )
				{
					mCand = mCands.mbrs[ mIdx ];
					// Copy the foregoing, not-deleted substring.
					if( (copiedLen = mCand->start - inTIdx) )
					{
						wmemcpy( ret + outTIdx, text + inTIdx, copiedLen );
						outTIdx += copiedLen;
						inTIdx += copiedLen;
					}
					// Copy the substitute string in place of the deleted substring.
					for( subChunkIdx = 0; subChunkIdx < nofSubChunks; subChunkIdx++ )
					{
						// If it is a verbatim substitute string,
						if( isVerbatim[ subChunkIdx ] )
						{
							wmemcpy( ret + outTIdx,
													subChunks[ subChunkIdx ],
						(subPartLen = subChunks[ subChunkIdx + 1 ] - subChunks[ subChunkIdx ]) );

							outTIdx += subPartLen;
						}
						// If the substitute string is a reference,
						else
						{
							// Either insert the matched parenthesized subregex.
							if( (refIdx = *subChunks[ subChunkIdx ] - L'0') )
							{
								// The arrays `parens', in contrast to references in the `subst' 
								// string, are zero-based.
								refIdx--;

								if( (subPartLen = mCand->parens[ refIdx ].end
												- mCand->parens[ refIdx ].begin) > 0 )
								{
									wmemcpy( ret + outTIdx,
															text + mCand->parens[ refIdx ].begin,
															subPartLen );
									outTIdx += subPartLen;
								}
							}
							// Or insert the string matched by the whole matcher,
							else
							{
								if( mCand->end - mCand->start )
								{
									wmemcpy( ret + outTIdx,
															text + mCand->start,
															mCand->end - mCand->start );
									outTIdx += mCand->end - mCand->start;
								}
							}
						}
					}
					inTIdx += mCand->end - mCand->start;
				}
				// Copy the last, not-deleted substring.
				wmemcpy( ret + outTIdx, text + inTIdx, inLen + 1 - inTIdx );

				RETURN( ret );
			}
		}
	}
	// If only the first occurrence shall be substituted,
	{
#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM /**/

		rxAnaRess *rress = rxCompile( regex, flags, rco );
		if( !rress )
		{
			RETURN( ERRET );
		}
#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM freeRress( rress )

		assignText( text, rress );
		cand *matcher = nextCand( rress );
		// If an exception occured,
		if( matcher->start == excCand.start &&
				matcher->end   == excCand.end )
		{
			RETURN( ERRET );
		}


		// If there is no matcher,
		if( matcher->start == invCand.start &&
			  matcher->end   == invCand.end )
		{
			// Return a copy of the input string.
			if( !( ret = (wchar_t*) malloc( (inLen + 1) * sizeof( wchar_t ) ) ) )
			{
				errno = ENOMEM;
				RETURN( ERRET );
			}
			RETURN( wmemcpy( ret, text, inLen + 1 ) );
		}

#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM disposeFreeCand( matcher, rress ), freeRress( rress )

		// If there is a matcher,
		else
		{
			// Find whether references are in use.
				// References may be disabled.
			_Bool usesRefs = !( flags & RF_NOSUB );
			unsigned char nofSubChunks;
			subLen = wcslen( subst );

				// Count number of references in the substitute string.
			if( usesRefs && subLen )
				nofSubChunks = countSubChunks( subst, subLen,
																			 rress->nofParens, &usesRefs );
			else
				usesRefs = 0;

			size_t outLen = inLen - ( matcher->end - matcher->start );

			// If the substitute string is verbatim,
			if( !usesRefs )
			{
				// Return the input string with the matcher substituted.
				subLen = wcslen( subst );
				if( !( ret = (wchar_t*) malloc(
									( inLen - (matcher->end - matcher->start) + subLen + 1 ) *
									sizeof( wchar_t ) ) ) )
				{
					errno = ENOMEM;
					RETURN( ERRET );
				}
				if( matcher->start )
					wmemcpy( ret, text, matcher->start );
				if( subLen )
					wmemcpy( ret + matcher->start, subst, subLen );
				wmemcpy( ret + matcher->start + subLen,
								 text + matcher->end,
								 inLen - matcher->end + 1 );
				RETURN( ret );
			} // if( !usesRefs )
			else
			{
				// The substitute string needs to be broken into several substitute 
				// substrings, either verbatim, or references.

				/* pointers to subsequent chunks of the substitute string: 
				 * verbatim-reference-verbatim-... */
				wchar_t **subChunks;
				// The last member of `subChunks' will be pointer after the last char of 
				// `subst'.
				SMALLOC( subChunks, nofSubChunks + 1, wchar_t* )
				/* whether each of the chunks is verbatim (as opposed to a reference) */
				_Bool *isVerbatim;
				SMALLOC( isVerbatim, nofSubChunks, _Bool )
				/* the substitute string unescaped */
				wchar_t *unescaped;
				SMALLOC( unescaped, subLen + 1, wchar_t )
				unsigned int unIdx, unLen;
#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM disposeFreeCand( matcher, rress ); freeRress( rress ); \
								FREE( subChunks ); FREE( unescaped ); FREE( isVerbatim );

				/* number how many times particular references will be used */
				unsigned int nofUses[ 1 + rress->nofParens ];
				memset( nofUses, 0, ( 1 + rress->nofParens ) * sizeof( unsigned int ) );

				// Count necessary size of the return string.
				// Create the unescaped substitute string.
				_Bool lastVerbatim = 0;
				t_idx subIdx;
				unsigned int subChunkIdx = 0;
				unIdx = 0;
					// Count numbers of different references,
				for( subIdx = 0; subIdx < subLen; subIdx++ )
				{
					if( subst[ subIdx ] == L'\\' )
					{
						// Read in the next char.
						// If a reference follows,
						if( L'0' <= subst[ ++subIdx ] &&
							subst[ subIdx ] <= (wchar_t) ( L'0' + rress->nofParens ) )
						{
							nofUses[ (wint_t) ( subst[ subIdx ] - L'0' ) ]++;
							subChunks[ subChunkIdx ] = unescaped + unIdx;
							unescaped[ unIdx++ ] = subst[ subIdx ];
								// Add the needed space for the last verbatim substitute substring.
							if( lastVerbatim && subChunkIdx )
								outLen += subChunks[ subChunkIdx ] - subChunks[ subChunkIdx - 1 ];
							lastVerbatim = isVerbatim[ subChunkIdx++ ] = 0;
						}
						else if( ! lastVerbatim )
						{
							subChunks[ subChunkIdx ] = unescaped + unIdx;
							lastVerbatim = isVerbatim[ subChunkIdx++ ] = 1;
							// Either the backslash served as an escape character:
								// If there exists a character after the backslash,
							if( subIdx < subLen )
								unescaped[ unIdx++ ] = subst[ subIdx ];
							// Or it was a literal backslash.
							else
								unescaped[ unIdx++ ] = subst[ subIdx - 1 ];
						}
					}
					// If verbatim string follows,
					else
					{
						// If it starts here,
						if( ! lastVerbatim )
						{
							subChunks[ subChunkIdx ] = unescaped + unIdx;
							lastVerbatim = isVerbatim[ subChunkIdx++ ] = 1;
						}
						unescaped[ unIdx++ ] = subst[ subIdx ];
					}
				}
				unescaped[ (unLen = unIdx) ] = L'\0';
				subChunks[ nofSubChunks ] = unescaped + unLen;
					// Add the needed space for the last verbatim substitute substring.
				if( lastVerbatim && subChunkIdx )
					outLen += subChunks[ subChunkIdx ] - subChunks[ subChunkIdx - 1 ];

						// Add the needed space for referenced matched substrings.
				begend be;
				unsigned int refIdx;
					// for the reference "\0":
				outLen += ( matcher->end - matcher->start ) * nofUses[ 0 ];
					// for all other references:
				for( refIdx = 1; refIdx <= rress->nofParens; refIdx++ )
				{
						// Add the parenthesized spans that were not skipped.
					be = matcher->parens[ refIdx - 1 ];
					outLen += (be.end > be.begin) ?
								( be.end - be.begin ) * nofUses[ refIdx ] : 0;
				}

				if( !( ret = (wchar_t*) malloc(
									( outLen + 1 ) * sizeof( wchar_t ) ) ) )
				{
					errno = ENOMEM;
					RETURN( ERRET );
				}

				// Perform the substitution.
				t_idx outTIdx = 0, inTIdx = 0, copiedLen;
				int subPartLen;
				// Copy the foregoing, not-deleted substring.
				if( (copiedLen = matcher->start - inTIdx) )
				{
					wmemcpy( ret + outTIdx, text + inTIdx, copiedLen );
					outTIdx += copiedLen;
					inTIdx += copiedLen;
				}
				// Copy the substitute string in place of the deleted substring.
				for( subChunkIdx = 0; subChunkIdx < nofSubChunks; subChunkIdx++ )
				{
					// If it is a verbatim substitute string,
					if( isVerbatim[ subChunkIdx ] )
					{
						wmemcpy( ret + outTIdx,
												subChunks[ subChunkIdx ],
					(subPartLen = subChunks[ subChunkIdx + 1 ] - subChunks[ subChunkIdx ]) );

						outTIdx += subPartLen;
					}
					// If the substitute string is a reference,
					else
					{
						// Either insert the matched parenthesized subregex.
						if( (refIdx = *subChunks[ subChunkIdx ] - L'0') )
						{
							// The arrays `parens', in contrast to references in the `subst' 
							// string, are zero-based.
							refIdx--;

							if( (subPartLen = matcher->parens[ refIdx ].end
											- matcher->parens[ refIdx ].begin) > 0 )
							{
								wmemcpy( ret + outTIdx,
														text + matcher->parens[ refIdx ].begin,
														subPartLen );
								outTIdx += subPartLen;
							}
						}
						// Or insert the string matched by the whole matcher,
						else
						{
							if( matcher->end - matcher->start )
							{
								wmemcpy( ret + outTIdx,
														text + matcher->start,
														matcher->end - matcher->start );
								outTIdx += matcher->end - matcher->start;
							}
						}
					}
				}
				inTIdx += matcher->end - matcher->start;
				// Copy the last, not-deleted substring.
				wmemcpy( ret + outTIdx, text + inTIdx, inLen + 1 - inTIdx );

				RETURN( ret );
			}
		}
	}
}

/** 
 * Counts number of chunks (verbatim/reference) into which a substitute string 
 * splits.
 *
 * Arguments:
 * 	subst			: the substitute string
 * 	subLen		: its length
 * 	nofParens	: number of parentheses in the matching regex
 * 	usesRefs	: pointer to where to store whether there are back references used 
 * 							in the substitute string
 */
static inline unsigned char countSubChunks(
			wchar_t *subst, size_t subLen, r_idx nofParens, _Bool *usesRefs )
{
	unsigned char nofRefs = 0;
	_Bool lastVerbatim = 0;
	t_idx subIdx;
	*usesRefs = 0;
	for( subIdx = 0; subIdx < subLen; subIdx++ )
	{
		if( subst[ subIdx ] == L'\\' &&
			// Read in the next char.
			// If a reference follows,
				L'0' <= subst[ ++subIdx ] &&
				subst[ subIdx ] <= (wchar_t) ( L'0' + nofParens ) )
		{
			nofRefs++;
			*usesRefs = 1;
			lastVerbatim = 0;
		}
		else if( ! lastVerbatim )
		{
			nofRefs++;
			lastVerbatim = 1;
		}
	}
	return nofRefs;
}

/**
 * Merges a candidates array, sorted by starts of candidates, into arrays of 
 * best candidates. It also frees memory allocated for the `matching' array.
 * 	Asserts `matching.limit'.
 *
 * Arguments:
 * 	matching	: the candidates array to be merged in
 * 	rress			: regex analysis resources
 *
 * Returns 1 iff the operation was successful.
 * Returns 0 iff not enough memory was available for allocation.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET 0
static inline _Bool mergeToBest( candArr *matching, rxAnaRess *const rress )
{
#ifdef DEBUG
	assert( matching->limit );
#endif

	cand *newCand, *curCand;
	cand_l *curCand_elm, *prevCand_elm, *newsPrev_elm;
	candsCluster *curCands;
	unsigned int candIdx;
	int newBetter;

	// Merge in the candidates one after another.
	for( candIdx = matching->limit - 1; candIdx != (unsigned int) -1; candIdx-- )
	{
nextNewCand:
		newCand = matching->mbrs[ candIdx ];
		curCands = &rress->bestCands[ newCand->start ];
		// If there are no best candidates for that start index yet,
		if( ! (curCand_elm = curCands->matchingCands) )
		{
			// Add the new candidate as the only one.
			SMALLOC( curCand_elm, 1, cand_l )
			curCand_elm->val = newCand;
			curCand_elm->next = NULL;
			curCands->matchingCands = curCand_elm;
			// Possibly update, which `candsCluster' is the first non-empty one.
			if( newCand->start < rress->firstStart )
				rress->firstStart = newCand->start;
		}
		else
		{
			newsPrev_elm = prevCand_elm = NULL;
			while( curCand_elm != NULL )
			{
				curCand = curCand_elm->val;
				// Compare the new cand with the existing one.
				if( (newBetter = compCands( newCand, curCand, rress )) )
				{
					// If the new candidate is better,
					if( newBetter == 2 )
					{
						// Disjoin the existing candidate from the chain.
						if( prevCand_elm )
						{
							prevCand_elm->next = curCand_elm->next;
							curCand_elm = prevCand_elm;
						}
						else
						{
							curCands->matchingCands = curCand_elm->next;
							FREE( curCand_elm );
							curCand_elm = NULL;
						}
						// Dispose the candidate.
						disposeFreeCand( curCand, rress );
					}
					// If the existing candidate was better,
					else if( newBetter == -2 )
					{
						// Dispose the new candidate.
						disposeFreeCand( newCand, rress );
						// Proceed to next new candidate.
						if( candIdx-- )
							goto nextNewCand;
						else
							goto lastNewCand;
					}
				}
				if( curCand_elm )
				{
					// Remember the position where to insert the new candidate.
					if( curCand->end < newCand->end )
						newsPrev_elm = curCand_elm;
					// Proceed to the next candidate in the chain.
					prevCand_elm = curCand_elm;
					curCand_elm = curCand_elm->next;
				}
				else
				{
					prevCand_elm = NULL;
					curCand_elm = curCands->matchingCands;
				}
			}
			// Insert the new candidate into the chain.
			SMALLOC( curCand_elm, 1, cand_l )
			curCand_elm->val = newCand;
			if( newsPrev_elm )
			{
				curCand_elm->next = newsPrev_elm->next;
				newsPrev_elm->next = curCand_elm;
			}
			else
			{
				curCand_elm->next = curCands->matchingCands;
				curCands->matchingCands = curCand_elm;
			}
		}
	}
lastNewCand:

	FREE( matching->mbrs );
	matching->limit = matching->cap = 0;

	return 1;
}

static void dumpRM( const void *nodep, VISIT value, int level )
{
	if( value == preorder || value == leaf )
		dumpedRM[ drmIdx++ ] = **((repMark**) nodep);
}

/**
 * Writes out all marks present in the marks tree and saves them in the global 
 * array `dumpedRM' and saves their count in `drmSize'.
 *
 * Returns `dumpedRM'.
 *
 * In case of exception, sets `errno' and returns NULL.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET NULL
static repMark *dumpMarksTree( void **marksTree )
{
	drmIdx = 0;
	SMALLOC( dumpedRM, 1000, repMark )
	twalk( *marksTree, dumpRM );
	drmSize = drmIdx;
	return dumpedRM;
}

/**
 * Checks that number of nodes linking to a repetition mark equals number of 
 * links according to all repetition marks.
 *
 * Returns:
 * 	 1	 	...if the counts are equal;
 * 	 0		...if the counts are NOT equal;
 * 	-1		...if an exception occured.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET -1
static signed char checkNofLinks( rxAnaRess *rress )
{
	int marksSrc = 0, marksTgt = 0, nodesSrc = 0;
	int markIdx, nodeIdx, candIdx;
	node *curNode;
	h_idx hIdx;
	h_elm hElm;

	if( ! dumpMarksTree( rress->marksTree ) )
		return ERRET;

	for( markIdx = 0; markIdx < drmSize; markIdx++ )
	{
		marksSrc += dumpedRM[ markIdx ].nofMarks;
		marksTgt += dumpedRM[ markIdx ].nofLinks;
	}
	for( nodeIdx = rress->nofNodes - 1; nodeIdx >= 0; nodeIdx-- )
	{
		curNode = &rress->allocNodes[ nodeIdx ];
		for( candIdx = curNode->lCands.limit - 1; candIdx >= 0; candIdx-- )
			for( hIdx = rress->nofReps - 1; hIdx != negHIdx; hIdx-- )
			{
				hElm = curNode->lCands.mbrs[ candIdx ]->hist[ hIdx ];
				nodesSrc += ( hElm.mark != NULL );
			}
		for( candIdx = curNode->nextLCands.limit - 1; candIdx >= 0; candIdx-- )
			for( hIdx = rress->nofReps - 1; hIdx != negHIdx; hIdx-- )
			{
				hElm = curNode->nextLCands.mbrs[ candIdx ]->hist[ hIdx ];
				nodesSrc += ( hElm.mark != NULL );
			}
		for( candIdx = curNode->rCands.limit - 1; candIdx >= 0; candIdx-- )
			for( hIdx = rress->nofReps - 1; hIdx != negHIdx; hIdx-- )
			{
				hElm = curNode->rCands.mbrs[ candIdx ]->hist[ hIdx ];
				nodesSrc += ( hElm.mark != NULL );
			}
		for( candIdx = curNode->nextRCands.limit - 1; candIdx >= 0; candIdx-- )
			for( hIdx = rress->nofReps - 1; hIdx != negHIdx; hIdx-- )
			{
				hElm = curNode->nextRCands.mbrs[ candIdx ]->hist[ hIdx ];
				nodesSrc += ( hElm.mark != NULL );
			}
	}
	FREE( dumpedRM );
	drmSize = 0;
	return (marksSrc + nodesSrc == marksTgt);
}

/**
 * Parses the regex into a syntactic tree. Asserts the regex is non-empty.
 *
 * Arguments:
 * 	regex : the regex to parse
 * 	flags	: flags modifying interpretation of `regex'
 *
 * Returns a pointer to clean regex resources describing `regex'.
 *
 * If an exception occurs, returns NULL.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET NULL
rxAnaRess *rxCompile( const wchar_t *const regex, rxFlags flags, rxCandOrdering rco )
{
#ifdef DEBUG
	assert( wcslen( regex ) > 0 );
#endif

	// Interpret the arguments.
	_Bool iCase = flags & RF_ICASE;
	rxType rtype = (flags & RF_EXTENDED) ? extended : basic;

	// Count number of needed nodes, atoms, and letters.
	r_idx curRIdx, futRIdx;
	wchar_t curChar, futChar;
		// `nofNodes' is set to 1 for the root node
	unsigned short nofNodes = 1, nofAtoms = 0,
								 nofLtrs = 0, nofProps = 0, nofReps = 0, nofParens = 0;
	unsigned short maxNofSubtrees = 1;
	_Bool enumerating = 0, enumFirst = 0, escaped = 0, newlyEscaped = 0;

#define COUNTS_TWICE (iCase && (towlower( curChar ) != towupper( curChar )))

	for( curRIdx = 0; (curChar = regex[ curRIdx ]) != L'\0'; curRIdx++ )
	{
		if( enumerating )
		{
				// Either this character ends the enumeration,
			if( curChar == L']' )
			{
				enumerating = 0;
			}
				// Or, this character introduces a POSIX character class,
			else if( (curChar == L'[') &&
							 (regex[ (futRIdx = curRIdx + 1) ] == L':') )
			{
				// Read all characters till L':'.
				while( (futChar = regex[ ++futRIdx ]) != L':' )
				{
					if( futChar == L'\0' )
					{
						errno = EINVAL;
						return ERRET;
					}
				}
				// The next one has to be L']'.
				if( regex[ ++futRIdx ] != L']' )
				{
					errno = EINVAL;
					return ERRET;
				}
				// Count in and skip all characters just processed.
				nofProps++;
				curRIdx = futRIdx;
			}
			else if( curChar == L'\\' )
			{
				switch( (curChar = regex[ ++curRIdx ]) )
				{
					case L'0':
					case L'1':
					case L'2':
					case L'3':
					case L'4':
					case L'5':
					case L'6':
					case L'7':
						curChar = btowc(
								parseOctal( regex[curRIdx++], regex[curRIdx++], regex[curRIdx] ) );
						nofLtrs += 1 + COUNTS_TWICE;
						break;

					case L'x':
					case L'X':
						curChar = btowc(
								parseHexa( regex[++curRIdx], regex[++curRIdx] ) );
						nofLtrs += 1 + COUNTS_TWICE;
						break;

// These cases shall be used only after including the regex type "vim-like".
//
// 					case L'a':
// 					case L'b':
// 					case L'f':
// 					case L'n':
// 					case L'r':
// 					case L't':
// 					case L'v':
// 						nofLtrs++;
// 						break;

					default:
						nofLtrs += 1 + COUNTS_TWICE;
				}
			}
			else
				nofLtrs += 1 + COUNTS_TWICE;
		}	// if( enumerating )

#define COUNT_COMMON	\
		nofNodes++;	\
		nofAtoms++;	\
		nofLtrs += 1 + (iCase && towlower( curChar ) != towupper( curChar ));

		else switch( curChar )
		{
			case L')':
				if( escaped ^ (rtype == basic) )
				{
					COUNT_COMMON
				}
				break;

			case L'+':
			case L'?':
				if( escaped ^ (rtype == basic) )
				{
					COUNT_COMMON
					break;
				}
			case L'*':
				if( escaped )
				{
					COUNT_COMMON
					break;
				}
				nofNodes++;
				nofReps++;
				break;

			case L'(':
				if( escaped ^ (rtype == basic) )
				{
					COUNT_COMMON
					break;
				}
				nofNodes++;
				maxNofSubtrees++;
				break;

			case L'|':
				if( escaped ^ (rtype == basic) )
				{
					COUNT_COMMON
					break;
				}
				nofNodes++;
				maxNofSubtrees++;
				break;

			case L'.':
				if( escaped )
				{
					COUNT_COMMON
					break;
				}
				nofNodes++;
				nofAtoms++;
				break;

			case L'[':
				if( escaped )
				{
					COUNT_COMMON
					break;
				}
				enumerating = 1;
				nofNodes++;
				nofAtoms++;
				if( regex[ curRIdx + 1 ] == L']' )
				{
					curRIdx++;
					nofLtrs++;
				}
				else if( regex[ curRIdx + 1 ] == L'^' )
					curRIdx++;
				break;

			case L'w':
			case L'W':
				if( escaped )
				{
					nofNodes++;
					nofAtoms++;
					nofProps++;
				}
				else
				{
					COUNT_COMMON
				}
				break;

			case L'{':
				if( escaped ^ (rtype == basic) )
				{
					COUNT_COMMON
					break;
				}
				nofNodes++;
				nofReps++;
				while( (curChar = regex[ ++curRIdx ]) != L'}' )
				{
					if( curChar == L'\0' )
					{
						errno = EINVAL;
						return ERRET;
					}
				}
				break;

			case L'\\':
				if( escaped )
				{
					COUNT_COMMON
				}
				else
					newlyEscaped = 1;
				break;

			default:						// case of a single letter, or an anchor
				COUNT_COMMON
		}
		escaped = newlyEscaped;
		newlyEscaped = 0;
	}

	/* preallocated structures */
	node* allocNodes = (node*) CALLOC( nofNodes, sizeof( node ) );
	r_idx nextFreeNode = 0;
	node *newNode, *adNode, *parToOpen, *firstRepd, *encNode, *outerEncNode;

	atom* allocAtoms = (atom*) CALLOC( nofAtoms, sizeof( atom ) );
	r_idx nextFreeAtom = 0;
	
	wchar_t* allocLtrs = (wchar_t*) CALLOC( nofLtrs, sizeof( wchar_t ) );
	r_idx nextFreeLtr = 0;

	wctype_t* allocProps = (wctype_t*) CALLOC( nofProps, sizeof( wctype_t ) );
	r_idx nextFreeProp = 0;

	/* repetition (operator) properties */
	repProp* repProps = (repProp*) CALLOC( nofReps, sizeof( repProp ) );
	h_idx* repPriors = (h_idx*) CALLOC( nofReps, sizeof( h_idx ) );
	r_idx nextFreeRep = 0;

	if( ! (allocNodes && allocAtoms && allocProps && allocLtrs && repProps && repPriors) )
	{
		errno = ENOMEM;
		return ERRET;
	}
	
	/* array of partial parse subtrees */
	node* subtrees[ maxNofSubtrees ];
	unsigned short nofSubtrees = 1;
	node* lastSubtree = NULL;
	/* depth of parentheses respective to the subtree */
	unsigned short parenLevel[ maxNofSubtrees ];
	parenLevel[0] = 0;
	unsigned short thisParLevel;
	/* index of the last subtree rooted in a '(', or 0 if none such exists */
	unsigned short lastRootPar = 0;
	/* array of the leftmost nodes in respective subtrees */
	node* leftNodes[ maxNofSubtrees ];
	/* array of the last ones of the nodes to be matched as first within a subtree 
	 * -- that have no link to an adjoined node */
	node* lastFirstNode[ maxNofSubtrees ];

	unsigned short nofEnumLtrs, nofEnumProps;
	wchar_t *thisLtrs;
	wctype_t *thisProps;

	// Build the tree.
	_Bool isLiteral;
	size_t rLen = wcslen( regex );
	char propName[ rLen <= 10 ? 7 : rLen - 3 ];
	r_idx pNameIdx;

#define CRASH	\
			FREE( allocNodes );	\
			FREE( allocAtoms );	\
			FREE( allocProps );	\
			FREE( allocLtrs );	\
			FREE( repProps );	\
			FREE( repPriors );	\
			return ERRET;

		// Initialize the node -- local properties.
	curRIdx = 0;
	enumerating = escaped = 0;
	while( (curChar = regex[ curRIdx++ ]) )
	{
		if( enumerating )
		{
				// Either this character ends the enumeration,
			if( !enumFirst && curChar == L']' )
			{
				enumerating = 0;
				newNode->atom->size = nofEnumLtrs;
				newNode->atom->propsSize = nofEnumProps;
				nextFreeLtr += nofEnumLtrs;
				nextFreeProp += nofEnumProps;
			}
				// Or, it may be negation of the enumeration,
			else if( enumFirst && curChar == L'^' )
			{
				newNode->atom->inverse = 1;
			}
				// Or, this character introduces a POSIX character class,
			else if( (curChar == L'[') &&
							 (regex[ (futRIdx = curRIdx) ] == L':') )
			{
				pNameIdx = 0;
				// Read all characters till L':'.
				while( (futChar = regex[ ++futRIdx ]) != L':' )
				{
					if( futChar == L'\0' )
					{
						errno = EINVAL;
						CRASH
					}
					if( (propName[ pNameIdx++ ] = wctob( futChar )) == EOF )
					{
						// FIXME Provide an appropriate `errno'.
						CRASH
					}
				}
				// The next one has to be L']'.
				if( regex[ ++futRIdx ] != L']' )
				{
					errno = EINVAL;
					CRASH
				}
				// Get the property.
				propName[ pNameIdx ] = L'\0';
				if( !(thisProps[ nofEnumProps++ ] = wctype( propName )) )
				{
					errno = EINVAL;
					CRASH
				}
				// Skip all characters just processed.
				curRIdx = futRIdx + 1;
			}
				// Or, this character expresses a literal character.
			else
			{
				if( curChar == L'\\' )
				{
					switch( (curChar = regex[ curRIdx ]) )
					{
						case L'0':
						case L'1':
						case L'2':
						case L'3':
						case L'4':
						case L'5':
						case L'6':
						case L'7':
							curChar = btowc(
									parseOctal( regex[curRIdx++], regex[curRIdx++], regex[curRIdx] ) );
							break;

						case L'x':
						case L'X':
							curChar = btowc(
									parseHexa( regex[++curRIdx], regex[++curRIdx] ) );
							break;

	// These cases shall be used only after including the regex type "vim-like".
	//
	//					 case L'a':
	//					 case L'b':
	//					 case L'f':
	//					 case L'n':
	//					 case L'r':
	//					 case L't':
	//					 case L'v':
	//						 nofLtrs++;
	//						 break;

						default:
							curRIdx++;
					}
				}

				if( iCase )
				{
					thisLtrs[ nofEnumLtrs ] = towlower( curChar );
					if( thisLtrs[ nofEnumLtrs++ ] != (curChar = towupper( curChar )) )
						thisLtrs[ nofEnumLtrs++ ] = curChar;
				}
				else
					thisLtrs[ nofEnumLtrs++ ] = curChar;
			}
			enumFirst = 0;
		}	// if( enumerating )

		else
		{
			newNode = allocNodes + nextFreeNode++;
			isLiteral = 0;
			switch( curChar )
			{

#define JOINLAST2TREES	\
	/* link the trees */	\
	subtrees[ nofSubtrees - 2 ]->right = subtrees[ nofSubtrees - 1 ];	\
	subtrees[ nofSubtrees - 1 ]->up = subtrees[ nofSubtrees - 2 ];	\
	subtrees[ nofSubtrees - 1 ]->isRight = 1;	\
	/* point to parToOpen */ \
	if( parenLevel[ nofSubtrees - 1 ] ) \
	{ \
		for( adNode = leftNodes[ nofSubtrees - 1 ];	\
							adNode != NULL; \
							adNode = adNode->adjoined ) \
		{ \
			parToOpen = adNode; \
			while( parToOpen->parToOpen )	\
				parToOpen = parToOpen->parToOpen;	\
			if( parToOpen != subtrees[ lastRootPar ] ) \
				parToOpen->parToOpen = subtrees[ lastRootPar ];	\
		} \
	} \
	/* mark adjoined nodes */	\
		/* case of a '(' */	\
	if( subtrees[ nofSubtrees - 2 ]->op == cat )	\
	{	\
		/* update `lastRootPar' */ \
		if( parenLevel[ nofSubtrees - 2 ] ) \
		{ \
			while( subtrees[ --lastRootPar ]->op != cat ) \
				; \
		} \
		else \
			lastRootPar = 0; \
		subtrees[ nofSubtrees - 2 ]->adjoined =	\
					leftNodes[ nofSubtrees - 1 ];	\
		if( subtrees[ nofSubtrees - 2 ]->left == NULL )	\
		{	\
			leftNodes[ nofSubtrees - 2 ] = leftNodes[ nofSubtrees - 1 ];	\
			lastFirstNode[ nofSubtrees - 2 ] =	\
						lastFirstNode[ nofSubtrees - 1 ];	\
		}	\
	}	\
		/* case of an operator like '|' */ \
	else	\
	{	\
		lastFirstNode[ nofSubtrees - 2 ]->adjoined = 	\
					leftNodes[ nofSubtrees - 1 ];	\
		lastFirstNode[ nofSubtrees - 2 ] =	\
					lastFirstNode[ nofSubtrees - 1 ];	\
	}	\
	lastSubtree = subtrees[ --nofSubtrees - 1 ];

				case L')':
					// It may be just a literal.
					if( escaped ^ (rtype == basic) )
					{
						isLiteral = 1;
						break;
					}
					// Otherwise, join subtrees inside the parentheses.
					while( nofSubtrees > 1 &&
									parenLevel[ nofSubtrees - 2 ] == parenLevel[ nofSubtrees - 1 ] )
					{
						JOINLAST2TREES
					}
					// Join to the preceding subtree.
					JOINLAST2TREES
					// Free the allocated `newNode'.
					nextFreeNode--;
					break;

				case L'(':
					// It may be just a literal.
					if( escaped ^ (rtype == basic) )
					{
						isLiteral = 1;
						break;
					}
					newNode->op = cat;
					newNode->lrOrder = ++nofParens;
					if( lastSubtree != NULL )
					{
						newNode->left = lastSubtree;
						lastSubtree->up = newNode;
					}
					else
						lastFirstNode[ nofSubtrees - 1 ] = leftNodes[ nofSubtrees - 1 ] = newNode;
					subtrees[ nofSubtrees - 1 ] = newNode;
					// Adjust the level of parentheses for the new subtree.
					parenLevel[ nofSubtrees ] = parenLevel[ nofSubtrees - 1 ] + 1;
					// Register this node as the last subtree rooted in '('.
					lastRootPar = nofSubtrees - 1;
					// Start a new subtree.
					lastSubtree = subtrees[ nofSubtrees++ ] = NULL;
					break;

				case L'+':
					if( escaped ^ (rtype == basic) )
					{
						isLiteral = 1;
						break;
					}
					newNode->op = rep;
					newNode->lrOrder =
						repProps[ nextFreeRep ].lrOrder = nextFreeRep;
					repProps[ nextFreeRep ].minReps = 1;
					repProps[ nextFreeRep ].maxReps = 0;
					repProps[ nextFreeRep++ ].isGreedy = 1;
					break;

				case L'?':
					if( escaped ^ (rtype == basic) )
					{
						isLiteral = 1;
						break;
					}
					newNode->op = rep;
					newNode->lrOrder =
						repProps[ nextFreeRep ].lrOrder = nextFreeRep;
					repProps[ nextFreeRep ].minReps = 0;
					repProps[ nextFreeRep ].maxReps = 1;
					repProps[ nextFreeRep++ ].isGreedy = 1;
					break;

				case L'*':
					if( escaped )
					{
						isLiteral = 1;
						break;
					}
					newNode->op = rep;
					newNode->lrOrder =
						repProps[ nextFreeRep ].lrOrder = nextFreeRep;
					repProps[ nextFreeRep ].minReps = 0;
					repProps[ nextFreeRep ].maxReps = 0;
					repProps[ nextFreeRep++ ].isGreedy = 1;
					break;

				case L'{':
					if( escaped ^ (rtype == basic) )
					{
						isLiteral = 1;
						break;
					}
					newNode->op = rep;
					newNode->lrOrder =
						repProps[ nextFreeRep ].lrOrder = nextFreeRep;
					repProps[ nextFreeRep ].minReps = parseUInt( regex, &curRIdx );
					// Either contains one number only,
					if( regex[ curRIdx++ ] == L'}' )
						repProps[ nextFreeRep ].maxReps = repProps[ nextFreeRep ].minReps;
					// or a range.
					else
					{
						repProps[ nextFreeRep ].maxReps = parseUInt( regex, &curRIdx );
						curRIdx++;
					}
					// curRIdx is now pointing to after '}'
					repProps[ nextFreeRep++ ].isGreedy = 1;
					break;

				case L'|':
					if( escaped ^ (rtype == basic) )
					{
						isLiteral = 1;
						break;
					}
					newNode->op = or;
					break;

				case L'.':
					if( escaped )
					{
						isLiteral = 1;
						break;
					}
					newNode->op = cat;
					newNode->atom = allocAtoms + nextFreeAtom++;
					break;

				case L'[':
					if( escaped )
					{
						isLiteral = 1;
						break;
					}
					// Initialize the new atom.
					newNode->op = cat;
					newNode->atom = allocAtoms + nextFreeAtom++;
					newNode->atom->ltrs = thisLtrs = allocLtrs + nextFreeLtr;
					newNode->atom->props = thisProps = allocProps + nextFreeProp;
					// Initialize enumerating.
					enumFirst = enumerating = 1;
					nofEnumProps = nofEnumLtrs = 0;
					break;

				case L'w':
				case L'W':
					if( escaped )
					{
						newNode->op = cat;
						newNode->atom = allocAtoms + nextFreeAtom++;
						newNode->atom->size = 0;
						newNode->atom->propsSize = 1;
						newNode->atom->props = allocProps + nextFreeProp++;
						newNode->atom->props[0] = wctype( "alnum" );
						newNode->atom->inverse = (curChar == L'W');
					}
					else
					{
						isLiteral = 1;
					}
					break;

				case L'\\':
					if( escaped )
					{
						isLiteral = 1;
					}
					else
					{
						newlyEscaped = 1;
						nextFreeNode--;
					}
					break;

				case L'<':
				case L'>':
				case L'b':
				case L'B':
					if( !escaped )
					{
						isLiteral = 1;
						break;
					}
					newNode->op = anchor;
					newNode->atom = allocAtoms + nextFreeAtom++;
					newNode->atom->size = 1;
					newNode->atom->ltrs = allocLtrs + nextFreeLtr++;
					newNode->atom->ltrs[0] = curChar;
					break;

				case L'^':
				case L'$':
					if( escaped )
					{
						isLiteral = 1;
						break;
					}
					newNode->op = anchor;
					newNode->atom = allocAtoms + nextFreeAtom++;
					newNode->atom->size = 1;
					newNode->atom->ltrs = allocLtrs + nextFreeLtr++;
					newNode->atom->ltrs[0] = curChar;
					break;

				default:						// case of a single letter
					isLiteral = 1;
					break;
			}
			escaped = newlyEscaped;
			newlyEscaped = 0;

			if( isLiteral )
			{
				newNode->op = cat;
				newNode->atom = allocAtoms + nextFreeAtom++;
				newNode->atom->ltrs = allocLtrs + nextFreeLtr++;
				newNode->atom->size = 1;
				if( iCase )
				{
					newNode->atom->ltrs[ 0 ] = towlower( curChar );
					if( newNode->atom->ltrs[ 0 ] != (curChar = towupper( curChar )) )
					{
						newNode->atom->ltrs[ 1 ] = curChar;
						nextFreeLtr++;
						newNode->atom->size++;
					}
				}
				else
					newNode->atom->ltrs[ 0 ] = curChar;
			}
			else if( curChar == L'(' || curChar == L')' || curChar == L'\\' )
				continue;

			// Adjust the structure of the tree according to the last operator,
			// except the case of '(' which is already coped with.

			// Set the global properties in surrounding of the node.
			switch( newNode->op )
			{
				// ^, $
				case anchor:
				// concatenation
				case cat:
					// The node may be the first one in the current subtree,
					if( lastSubtree == NULL )
						lastFirstNode[ nofSubtrees - 1 ] = leftNodes[ nofSubtrees - 1 ] = newNode;
					// or it can continue after others.
					else
					{
						newNode->left = lastSubtree;
						lastSubtree->up = newNode;
					}
					// Anyway, it becomes the new root of the subtree.
					lastSubtree = subtrees[ nofSubtrees - 1 ] = newNode;
					break;

				// repeating the last atom
				case rep:
					// Update the link to start of the repeated subexpression.
						// The subexpression might have been like '(...)'.
					if( isOpeningPar( subtrees[ nofSubtrees - 1 ] ) )
						firstRepd = subtrees[ nofSubtrees - 1 ]->adjoined;
						// Or, its root might have been a repetition operator again.
					else if( subtrees[ nofSubtrees - 1 ]->op == rep )
						firstRepd = repProps[ subtrees[ nofSubtrees - 1 ]->lrOrder ].firstRepd;
						// Or, its root is just a catenated atom, or an anchor.
					else
						firstRepd = subtrees[ nofSubtrees - 1 ];
					repProps[ newNode->lrOrder ].firstRepd = firstRepd;

					// Update the `enclRep' link.
					for( encNode = firstRepd + 1; encNode != newNode; encNode++ )
					{
						if( encNode->op != rep )
							continue;
						while( (outerEncNode = repProps[ encNode->lrOrder ].enclRep) )
							encNode = outerEncNode;
						repProps[ encNode->lrOrder ].enclRep = newNode;
					}
					/* (The following loop is the cause for this function having 
					 * complexity of O(R^3).) */
					// Update the `startedRep' link.
					for( adNode = firstRepd; adNode != NULL; adNode = adNode->adjoined )
					{
						encNode = adNode;
						while( encNode->startedRep != NULL )
							encNode = encNode->startedRep;
						if( encNode != newNode )
							encNode->startedRep = newNode;
					}

					for( adNode = firstRepd; adNode->adjoined != NULL; adNode = adNode->adjoined )
						;
					// If the repeated subexpression may be skipped, link from there to this 
					// operator.
					if( repProps[ newNode->lrOrder ].minReps == 0 )
					{
						adNode->adjoined = newNode;
						if( adNode == lastFirstNode[ nofSubtrees - 1 ] )
							lastFirstNode[ nofSubtrees - 1 ] = newNode;
					}
					// Update the `firstEnRep' datum.
					for( encNode = repProps[ newNode->lrOrder ].firstRepd + 1;
										encNode->op != rep;
										encNode++ )
								;
					repProps[ newNode->lrOrder ].firstEnRep = encNode->lrOrder;
					// Build in the node.
					newNode->left = lastSubtree;
					lastSubtree->up = newNode;
					lastSubtree = subtrees[ nofSubtrees - 1 ] = newNode;
					break;

				// |
				case or:
					// Build in the new node.
					newNode->left = lastSubtree;
					lastSubtree->up = newNode;
					subtrees[ nofSubtrees - 1 ] = newNode;
					// Wait for the second operand.
					parenLevel[ nofSubtrees ] = parenLevel[ nofSubtrees - 1 ];
					lastSubtree = subtrees[ nofSubtrees++ ] = NULL;
					break;

			}
		}
		
	}

	// Join all subtrees.
	while( nofSubtrees > 1 )
	{
		JOINLAST2TREES
	}

	// Provide the tree with a root.
	node* root = allocNodes + nextFreeNode++;
	root->op = top;
	root->left = subtrees[0];
	subtrees[0]->up = root;

#ifdef DEBUG
	assert( nextFreeNode == nofNodes );
	assert( nextFreeAtom == nofAtoms );
	assert( nextFreeProp == nofProps );
	assert( nextFreeLtr == nofLtrs );
#endif

	// Count depth for each node, and the maximum depth.
	// Also count "order" of repetition operators (or their "nestedness").
	node* curNode = root->left;
	r_idx curDepth = 1, maxDepth = 1;
	dir comingFrom = up, goingTo = left;
	while( curNode != root )
	{
		switch( comingFrom )
		{
			case up:
				// The depth of nodes is set here.
				curNode->depth = curDepth;
				goingTo = left;
				break;
			case left:
				goingTo = right;
				break;
			case right:
				goingTo = up;
		}
		switch( goingTo )
		{
			case left:
				// The repetition order is set here.
				if( curNode->op == rep )
				{
					repProps[ curNode->lrOrder ].order =
								(outerEncNode = repProps[ curNode->lrOrder ].enclRep) ?
								repProps[ outerEncNode->lrOrder ].order + 1 : 0;
					// Repetition operators always have a left son.
					curNode = curNode->left;
					curDepth++;
					break;
				}
				else if( curNode->left != NULL )
				{
					curNode = curNode->left;
					curDepth++;
					break;
				}
			case right:
				if( curNode->right != NULL )
				{
					comingFrom = up;
					curNode = curNode->right;
					curDepth++;
					break;
				}
			case up:
				comingFrom = curNode->isRight ? right : left;
				// The max depth is counted here.
				maxDepth = curDepth > maxDepth ? curDepth : maxDepth;
				curDepth--;
				curNode = curNode->up;
		}
	}

	/* array of linked lists for active nodes */
	node** actNodes = (node**) CALLOC( maxDepth + 1, sizeof( node* ) );
	/* array of linked lists for next active nodes */
	node** nextActNodes = (node**) CALLOC( maxDepth + 1, sizeof( node* ) );

	if( !actNodes || !nextActNodes )
	{
		errno = ENOMEM;
		return ERRET;
	}

	// Mark starting nodes.
	node* lastStartNode = leftNodes[0];
	do
	{
		// Mark the node as starting and next active.
		lastStartNode->isStartNode = lastStartNode->isNActive = 1;
		// Join it in the linked lists of next active nodes.
		curDepth = lastStartNode->depth;
		lastStartNode->nextNAct = nextActNodes[ curDepth ];
		nextActNodes[ curDepth ] = lastStartNode;
	} while( (lastStartNode = lastStartNode->adjoined) != NULL );

	// Sort history indices.
	if( nofReps )
	{
		h_idx curRepIdx;
		annRepProp annRepProps[ nofReps ];
		rxCandOrdering rcoDirs = rco & RCO_DIRMASK;
		switch( rco & RCO_WMASK )
		{
			case 1:
				annRepProps[ 0 ].oMagn = 2;
				annRepProps[ 0 ].lMagn = 0;
				annRepProps[ 0 ].gMagn = 1;
				break;

			case 2:
				annRepProps[ 0 ].oMagn = 1;
				annRepProps[ 0 ].lMagn = 2;
				annRepProps[ 0 ].gMagn = 0;
				break;

			case 3:
				annRepProps[ 0 ].oMagn = 1;
				annRepProps[ 0 ].lMagn = 0;
				annRepProps[ 0 ].gMagn = 2;
				break;

			case 4:
				annRepProps[ 0 ].oMagn = 0;
				annRepProps[ 0 ].lMagn = 2;
				annRepProps[ 0 ].gMagn = 1;
				break;

			case 5:
				annRepProps[ 0 ].oMagn = 0;
				annRepProps[ 0 ].lMagn = 1;
				annRepProps[ 0 ].gMagn = 2;
				break;

			default:
				annRepProps[ 0 ].oMagn = 2;
				annRepProps[ 0 ].lMagn = 1;
				annRepProps[ 0 ].gMagn = 0;
		}
		annRepProps[ 0 ].oDir = !( rcoDirs & RCO_O_DESC );
		annRepProps[ 0 ].lDir = !( rcoDirs & RCO_L_DESC );
		annRepProps[ 0 ].gDir = rcoDirs & RCO_G_ASC;
		annRepProps[ 0 ].val = repProps[ 0 ];
		for( curRepIdx = 1; curRepIdx < nofReps; curRepIdx++ )
		{
			annRepProps[ curRepIdx ] = annRepProps[ 0 ];
			annRepProps[ curRepIdx ].val = repProps[ curRepIdx ];
		}
		qsort( annRepProps, nofReps, sizeof( annRepProp ), compRepProps );
		for( curRepIdx = 0; curRepIdx < nofReps; curRepIdx++ )
		{
			repProps[ curRepIdx ] = annRepProps[ curRepIdx ].val;
			repPriors[ repProps[ curRepIdx ].lrOrder ] = curRepIdx;
		}
	}

	// Save all useful data to return them.
	rxAnaRess *rress;
	if( ! (rress = (rxAnaRess*) malloc( sizeof( rxAnaRess ) )) )
	{
		errno = ENOMEM;
		return ERRET;
	}
	rress->allocNodes = allocNodes;
	rress->nofNodes = nextFreeNode;
	rress->allocAtoms = allocAtoms;
	rress->allocLtrs = allocLtrs;
	rress->allocProps = allocProps;
	r_idx parenIdx;
	rress->nofParens = nofParens < MAX_DIFF_REFS ? nofParens : MAX_DIFF_REFS - 1;
	SMALLOC( rress->initParens, rress->nofParens, begend );
	for( parenIdx = rress->nofParens - 1; parenIdx != negRIdx; parenIdx-- )
		rress->initParens[ parenIdx ] = invBegend;
	rress->tree = root;
	rress->firstStartNode = leftNodes[0];
	rress->depth = maxDepth;
	rress->actNodes = actNodes;
	rress->nextActNodes = nextActNodes;
	rress->repProps = repProps;
	rress->repPriors = repPriors;
	rress->nofReps = nofReps;
	SCALLOC( rress->marksTree, 1, void* )
	rress->isClean = 1;
	rress->bestCands = NULL;
	return rress;
	// TODO (optimisation) Decide whether the empty string is accepted now.
}

/**
 * Runs the next input character through the regex tree. The next character is 
 * determined using `rress->text', `rress->nextTIdx', and `rress->textLen'. If 
 * (rress->nextTIdx == rress->textLen), an empty string is processed.
 * 
 * Arguments:
 * 		rress	: resources for the regex
 *
 * Returns an array of candidates that matched firstly after this character.
 * If an exception occurs, the returned array is equal to `excCArr' (which is 
 * invalid).
 *
 * Exceptions:
 * 		(errno = )
 * 		ERANGE			: too many repetitions as instantiation of a rep. op.
 * 		ENOMEM			: not enough memory available
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET excCArr
static candArr processChar( rxAnaRess *const rress )
{
	// Interpret the arguments.
	wchar_t curChar;					// currently processed character
	_Bool inEmpty;						// processing an empty string?
	t_idx startIdx;						// `start' for new candidates; also `end' for 
														// `lCands' of the root node
	if( rress->nextTIdx == rress->textLen )
		inEmpty = 1;
	else
		inEmpty = 0;

	curChar = rress->text[ rress->nextTIdx ];
	startIdx = rress->nextTIdx;

	// Set new active nodes from `nextActNodes'.
		// Swap arrays of active and new active nodes.
	node** nodepp = rress->actNodes;
	rress->actNodes = rress->nextActNodes;
	rress->nextActNodes = nodepp;
	r_idx curDepth;						// current depth (in the parse tree)
	node* curNode;						// currently processed node

		// Clear `nextActNodes'.
	memset( rress->nextActNodes, 0, (rress->depth + 1) * sizeof( node* ) );

		// Mark nodes to be processed as active and link them together.
	for( curDepth = rress->depth; curDepth > 0; curDepth-- )
	{
		if( (curNode = rress->actNodes[ curDepth ]) != NULL )
		{
			curNode->isNActive = 0;
			curNode->isActive = 1;
			while( (curNode = curNode->nextAct = curNode->nextNAct) != NULL )
			{
				curNode->isNActive = 0;
				curNode->isActive = 1;
			}
		}
	}

	// Create new candidates and put them into the tree.
	node *startNode = rress->firstStartNode, *parToOpen;
	cand *newCand;
	size_t newCSize;
	candsCluster *curCands = rress->bestCands + startIdx;

	do
	{
		// Create a copy of the new candidate.
		SMALLOC( newCand, 1, cand )
		newCand->start = startIdx;
		if( rress->nofParens )
		{
			SMALLOC( newCand->parens, rress->nofParens, begend )
			memcpy( newCand->parens, rress->initParens, rress->nofParens * sizeof( begend ) );
			// Open parentheses for the candidates.
			for( parToOpen = startNode->parToOpen;
								parToOpen != NULL;
								parToOpen = parToOpen->parToOpen )
			{
				if( parToOpen->lrOrder < MAX_DIFF_REFS )
					newCand->parens[ parToOpen->lrOrder - 1 ].begin = rress->nextTIdx;
			}
		}
		if( rress->nofReps )
		{
			SCALLOC( newCand->hist, rress->nofReps, h_elm )
		}
		// If `bestCands' is in use, register this candidate.
		if( rress->bestCands )
			curCands->nofCandsInTree++;
		// Append it to `startNode''s `nextLCands', moving `nextLCands' to `lCands'.
		newCSize = (startNode->nextLCands.limit + 1) * sizeof( cand* );
		SMALLOC( startNode->lCands.mbrs,
						 (startNode->nextLCands.limit + 1),
						 cand* )
		startNode->lCands.cap =
					startNode->lCands.limit = startNode->nextLCands.limit + 1;
		startNode->lCands.mbrs[ startNode->lCands.limit - 1 ] = newCand;
		if( startNode->nextLCands.cap )
		{
			memcpy( startNode->lCands.mbrs,
							startNode->nextLCands.mbrs,
							newCSize - sizeof( cand* ) );
			FREE( startNode->nextLCands.mbrs );
		}
		startNode->nextLCands.limit =
					startNode->nextLCands.cap = 0;
		startNode->lastTIdx = startIdx;
	} while( (startNode = startNode->adjoined) != NULL );
	rress->isClean = 0;

	// Traverse the regex tree, updating sets of candidates.
	r_idx newDepth;
	h_idx hIdx, encHIdx;
	node *adNode;
	cand **origCands, **newCands;
	cand *origCand, *curCand;
	unsigned int candIdx, newCandIdx, upCandIdx;
	candArr cArr, upCArr, backCArr, cArrToDisp, cArrToOpen, cArrCopy;
	cArrToOpen.isFree = upCArr.isFree = backCArr.isFree = 0;
	size_t nofCands;
	_Bool anchMatches, anchMatchesNext, isGreedy;
	unsigned int repCnt, minReps, maxReps;
	unsigned int markIdx, nofMarks;
	repMark *newMark;
	h_elm *hElm;

		// For each level (from the deepest one),
	for( curDepth = rress->depth, newDepth = curDepth - 1;
					curDepth > 0;
					curDepth = newDepth-- )
	{
		// For each active node at the level,
		for( curNode = rress->actNodes[ curDepth ];
						curNode != NULL;
						curNode = rress->actNodes[ curDepth ] )
		{
			updNode( curNode, startIdx );
			// Mark the `curNode' as processed.
			curNode->isActive = 0;
			rress->actNodes[ curDepth ] = curNode->nextAct;

			// Process the node.
			switch( curNode->op )
			{
				case cat:
					if( curNode->atom == NULL )	// in the case of '('
					{
						hIdx = curNode->lrOrder - 1;
						// Send any candidates from inside the parenthesized expr. up.
						if( (nofCands = curNode->rCands.limit) )
						{
							// Mark this t_idx as end of the parentheses in each cand.
							for( candIdx = 0; candIdx < nofCands; candIdx++ )
								curNode->rCands.mbrs[ candIdx ]->parens[ hIdx ].end = startIdx;
							if( ! (sendUp( curNode, &curNode->rCands, curDepth, 
													&newDepth, rress )) )
								return ERRET;
						}
						if( (nofCands = curNode->nextRCands.limit) )
						{
							// Mark the next t_idx as end of the parentheses in each cand.
							for( candIdx = 0; candIdx < nofCands; candIdx++ )
								curNode->nextRCands.mbrs[ candIdx ]->parens[ hIdx ].end = startIdx + 1;
							if( ! sendUpToNext( curNode, &curNode->nextRCands, curDepth, 
														&newDepth, rress ) )
								return ERRET;
						}
						// Candidates coming from left already have been sent to the 
						// parenthesized expression via the `adjoined' link.
						if( curNode->lCands.limit )
						{
							if( ! (disposeCands( &curNode->lCands, rress )) )
								return ERRET;
						}

						if( curNode->nextLCands.limit )
						{
							if( ! (disposeCands( &curNode->nextLCands, rress )) )
								return ERRET;
						}

						break;
					}
					// Following is done for catenating exactly one character.
					else
					{
						// If some candidates are waiting to get through,
						if( curNode->lCands.limit )
						{
							// Filter candidates.
							_Bool charMatches;
							if( inEmpty )
								charMatches = 0;
							else
							{
								// '.' matches everything
								if( !( charMatches = isDot( curNode ) ) )
								{
									// Test for literal match.
									r_idx ltrIdx;
									for( ltrIdx = curNode->atom->size - 1; ltrIdx != negRIdx; ltrIdx-- )
									{
										if( curChar == curNode->atom->ltrs[ ltrIdx ] )
										{
											charMatches = 1;
											break;
										}
									}
									// Test for matching a class.
									if( !charMatches )
									{
										r_idx propIdx;
										for( propIdx = curNode->atom->propsSize - 1; propIdx != negRIdx; propIdx-- )
										{
// 											if( ( 0 != iswctype( curChar, curNode->atom->props[ propIdx ] ) ) ^
// 														curNode->atom->propInverse[ propIdx ] )
											if( iswctype( curChar, curNode->atom->props[ propIdx ] ) )
											{
												charMatches = 1;
												break;
											}
										}
									}
									charMatches ^= curNode->atom->inverse;
								}
							}
							// If the candidates survived, send them up.
							if( charMatches )
							{
								// If this node opens a repetition, write it in the candidates.
								if( ! (openReps( curNode->lCands,
													curNode->startedRep, startIdx, rress )) )
									return ERRET;
								// If this node opens parentheses, write it in the candidates.
								openParens( curNode->lCands, curNode->parToOpen, startIdx, rress );

								if( ! sendUpToNext( curNode, &curNode->lCands, curDepth, 
															&newDepth, rress ) )
									return ERRET;
							}
							else
								if( ! (disposeCands( &curNode->lCands, rress )) )
									return ERRET;

						}
						// Schedule this node for being active next time if some candidates 
						// are waiting here for the next input character.
						if( curNode->nextLCands.limit )
						{
							if( ! curNode->isNActive )
							{
								curNode->isNActive = 1;
								curNode->nextNAct = rress->nextActNodes[ curDepth ];
								rress->nextActNodes[ curDepth ] = curNode;
							}
						}
					}
					break;

				case rep:
#ifdef DEBUG
					assert( curNode->lCands.limit | curNode->nextLCands.limit );
#endif
					hIdx = rress->repPriors[ curNode->lrOrder ];
					isGreedy = rress->repProps[ hIdx ].isGreedy;
					minReps = rress->repProps[ hIdx ].minReps;
					maxReps = rress->repProps[ hIdx ].maxReps;
					// Handle candidates with zero or infinity repetitions.
						// If there are some candidates that have not used the input char,
					if( (nofCands = curNode->lCands.limit) )
					{
						/* array for candidates to have this repetition open before 
						 * continuing upwards */
						cArrToOpen.mbrs = (cand**) MALLOC(
									( cArrToOpen.cap = nofCands ) * sizeof( cand* ) );
						cArrToOpen.limit = 0;
						/* array for candidates continuing up */
						upCArr.mbrs = (cand**) MALLOC(
									( upCArr.cap = nofCands ) * sizeof( cand* ) );
						upCArr.limit = 0;

						// Check the allocation was successful.
						if( !cArrToOpen.mbrs || !upCArr.mbrs )
						{
							errno = ENOMEM;
							return ERRET;
						}
#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM FREE( cArrToOpen.mbrs ), FREE( upCArr.mbrs )

						origCands = curNode->lCands.mbrs;
						for( candIdx = 0; candIdx < nofCands; candIdx++ )
						{
							origCand = origCands[ candIdx ];
							// Count the just-finished repetition.
							if( (hElm = origCand->hist + hIdx)->isOpen )
							{
#ifdef DEBUG
								// Assert that this candidate can repeat unbounded number of 
								// times on this repetition,
								assert( hElm->start == startIdx );
#endif
								// If he has known about it already,
								if( hElm->unbounded )
								{
									// He was here this `startIdx' already; dispose him.
									if( ! (disposeCand( origCand, rress )) )
									{
										FREEMEM;
										return ERRET;
									}
								}
								else
								{
									// Send him up - no rep. count can be better than unbounded.
									if( hElm->mark )
									{
										hElm->repCnt = 1 + getBestRepCnt( hElm->mark,
																											minReps ? minReps - 1 : 0,
																											maxReps - 1, isGreedy );
										// Close this repetition.
										if( ! (disposeTR( curCand, hIdx, rress )) )
										{
											FREEMEM;
											return ERRET;
										}
										hElm->mark = NULL;
									}
									if( maxReps && hElm->repCnt > maxReps )
										disposeCand( origCand, rress );
									else
									{
										hElm->unbounded = 1;
										hElm->used = 1;
										hElm->isOpen = 0;
										hElm->start = startIdx;
										upCArr.mbrs[ upCArr.limit++ ] = origCand;
									}
								}
							}
							else
							{
								// This candidate has the repetition instantiated zero times.
								hElm->used = 1;
								hElm->unbounded = hElm->repCnt = 0;
								hElm->start = startIdx;
								cArrToOpen.mbrs[ cArrToOpen.limit++ ] = origCand;
							}
						}
						// Mark the original array of candidates empty.
						FREE( curNode->lCands.mbrs );
						curNode->lCands.cap = curNode->lCands.limit = 0;
						// If there are some candidates waiting to have open enclosing 
						// repetitions,
						if( (nofCands = cArrToOpen.limit) )
						{
							// Open them the repetitions.
							if( ! (openReps( cArrToOpen, curNode->startedRep, startIdx, rress )) )
							{
								FREEMEM;
								return ERRET;
							}
							// Open them the parentheses, too.
							openParens( cArrToOpen, curNode->parToOpen, startIdx, rress );

							// Send them up.
							if( isInvCArr( upCArr = mergeCands( &upCArr, &cArrToOpen, rress ) ) )
							{
								FREEMEM;
								return ERRET;
							}
						}
						else
						{
							FREE( cArrToOpen.mbrs );
							cArrToOpen.cap = cArrToOpen.limit = 0;
						}
#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM FREE( upCArr.mbrs )

						if( upCArr.limit )
						{
							// Send the candidates up.
							if( ! (sendUp( curNode, &upCArr, curDepth, &newDepth, 
													rress )) )
							{
								FREEMEM;
								return ERRET;
							}
						}
						else
						{
							FREE( upCArr.mbrs );
							upCArr.cap = upCArr.limit = 0;
						}
					}

					// Handle candidates that have consumed the input char.
					if( (nofCands = curNode->nextLCands.limit) )
					{
						origCands = curNode->nextLCands.mbrs;
						/* array for candidates to have this repetition open before 
						 * continuing upwards */
						cArrToOpen.mbrs = (cand**) MALLOC( ( cArrToOpen.cap = nofCands ) * sizeof( cand* ) );
						cArrToOpen.limit = 0;
						/* array for candidates continuing up */
						upCArr.mbrs = (cand**) MALLOC( ( upCArr.cap = nofCands ) * sizeof( cand* ) );
						upCArr.limit = 0;
						/* array for candidates sent back to start of the repetition */
						backCArr.mbrs = (cand**) MALLOC( ( backCArr.cap = nofCands ) * sizeof( cand* ) );
						backCArr.limit = 0;

						// Check the allocation was successful.
						if( ! (cArrToOpen.mbrs && upCArr.mbrs && backCArr.mbrs ) )
						{
							errno = ENOMEM;
							return ERRET;
						}
#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM FREE( cArrToOpen.mbrs ), FREE( upCArr.mbrs ), FREE( backCArr.mbrs )

						/* array of candidates to be disposed */
						cArrToDisp = curNode->nextLCands;
						cArrToDisp.limit = 0;

						// Increment number of repetitions for each coming candidate.
						// Remove candidates with too big numbers of repetitions.
						// Divide candidates into arrays, based on where they continue.
							// If the number of repetitions is expressed using a text 
							// reference,
						if( rress->repProps[ hIdx ].order )
						{
							_Bool goesUp, goesBack;
							for( candIdx = 0; candIdx < nofCands; candIdx++ )
							{
								curCand = origCands[ candIdx ];
								hElm = curCand->hist + hIdx;
								// Special case: the repeated subexpression has been skipped, 
								// `minReps' == 0.
								if( ! hElm->isOpen )
								{
									cArrToOpen.mbrs[ cArrToOpen.limit++ ] = curCand;
									continue;
								}

								hElm->repCnt = hElm->mark ? 1 + getBestRepCnt( hElm->mark,
																									minReps ? minReps - 1 : 0,
																									maxReps - 1, isGreedy )
																					: 0;

								// Determine where to send this candidate.
									// Both unbounded number of repetitions till here and empty 
									// matching string cause the candidate to continue up.
									//   If it reaches unbounded count of repetitions, it shall 
									// not be sent back to the start of the repetition.
								if( (goesUp = ( hElm->unbounded |= hElm->start == startIdx + 1 )) )
									goesBack = 0;
								else
								{
									goesBack = ( !maxReps | (hElm->repCnt < maxReps) ) ||
														 ( maxReps > 1 &&
															 ( (0 == hElm->mark->nofMarks) ||
																 (hElm->mark->repCnt[0] + 1 < maxReps) ) );
									goesUp = hElm->repCnt >= minReps;
								}
								// Copy the candidate to arrays of cand.s continuing up, or 
								// back, as appropriate.
								if( goesBack )
									backCArr.mbrs[ backCArr.limit++ ] = curCand;

								if( goesUp )
									upCArr.mbrs[ upCArr.limit++ ] = curCand;
								else
									cArrToDisp.mbrs[ cArrToDisp.limit++ ] = curCand;
							}
						}
							// The number of repetitions is expressed literally.
						else
						{
								// Either there is an upper limit on number of rep.s,
							if( maxReps )
							{
								for( candIdx = 0; candIdx < nofCands; candIdx++ )
								{
									curCand = origCands[ candIdx ];
									// Special case: the repeated subexpression has been skipped, 
									// `minReps' == 0.
									if( ! (hElm = curCand->hist + hIdx)->isOpen )
									{
										cArrToOpen.mbrs[ cArrToOpen.limit++ ] = curCand;
										continue;
									}

									repCnt = ++hElm->repCnt;
									// Only if the repetition is not unbounded,
									// and there is some room to repeat yet,
									if( ! (hElm->unbounded |= ( hElm->start == startIdx + 1  )) &&
											( repCnt < maxReps ) )
									{
										// Send the candidate back.
										backCArr.mbrs[ backCArr.limit++ ] = curCand;
									}

									if( repCnt >= minReps )
										upCArr.mbrs[ upCArr.limit++ ] = curCand;
									else
										cArrToDisp.mbrs[ cArrToDisp.limit++ ] = curCand;
									// Check potential overflow.
									if( repCnt == 0 )
									{
										FREEMEM;
										errno = ERANGE;
										return ERRET;
									}
								}
							}
								// Or, the number of repetitions may be unbounded.
							else
							{
								for( candIdx = 0; candIdx < nofCands; candIdx++ )
								{
									curCand = origCands[ candIdx ];
									// Special case: the repeated subexpression has been skipped, 
									// `minReps' == 0.
									if( ! (hElm = curCand->hist + hIdx)->isOpen )
									{
										cArrToOpen.mbrs[ cArrToOpen.limit++ ] = curCand;
										continue;
									}

									// Only if the repetition is not unbounded,
									if( ! (hElm->unbounded |= ( hElm->start == startIdx + 1  )) )
									{
										// Send the candidate back.
										backCArr.mbrs[ backCArr.limit++ ] = curCand;
									}

									if( ++hElm->repCnt >= minReps )
										upCArr.mbrs[ upCArr.limit++ ] = curCand;
									else
										cArrToDisp.mbrs[ cArrToDisp.limit++ ] = curCand;
									// Check potential overflow.
									if( hElm->repCnt == 0 )
									{
										FREEMEM;
										errno = ERANGE;
										return ERRET;
									}
								}
							}
						}

						// Send the candidates to the node starting the repeated subexpr.
						if( (nofCands = backCArr.limit) )
						{
							adNode = rress->repProps[ hIdx ].firstRepd;
							do
							{
								// Clone the candidates.
								if( isInvCArr( cArrCopy = cloneCArr( backCArr, rress ) ) )
								{
									FREEMEM;
									return ERRET;
								}
								// For each new candidate,
								newCands = cArrCopy.mbrs;
								for( candIdx = 0; candIdx < nofCands; candIdx++ )
								{
									newCand = newCands[ candIdx ];
									// Mark all intervening repetitions as not used.
									for( encHIdx = rress->repProps[ hIdx ].firstEnRep;
														encHIdx < curNode->lrOrder;
														encHIdx++ )
									{
										hElm = newCand->hist + rress->repPriors[ encHIdx ];
#ifdef DEBUG
										assert( ! hElm->isOpen );
#endif
										hElm->used = 0;
									}
									// Mark new start of this repetition.
									hElm = newCand->hist + hIdx;
										// Shift the mark, if the candidate uses it.
									if( hElm->mark )
									{
										if( ! (newMark = addRepMark( startIdx + 1, hIdx, newCand->start,
																								 hElm->start, hIdx, rress )) ||
												! disposeTR( newCand, hIdx, rress ) )
										{
											FREEMEM;
											return ERRET;
										}
										hElm->mark = newMark;
									}
										// Mark the new start index.
									hElm->start = startIdx + 1;
								}
								// Send the candidates to the node.
								updNode( adNode, startIdx );
								if( isInvCArr( adNode->nextLCands =
																		mergeCands( &adNode->nextLCands,
																								&cArrCopy,
																								rress ) ) )
								{
									FREEMEM;
									return ERRET;
								}
								// Schedule the node to become active.
								if( ! adNode->isActive )
								{
									adNode->isActive = 1;
									adNode->nextAct = rress->actNodes[ adNode->depth ];
									rress->actNodes[ adNode->depth ] = adNode;
									newDepth = newDepth > adNode->depth ? newDepth : adNode->depth;
								}
							} while( (adNode = adNode->adjoined) && adNode < curNode );
						}
						FREE( backCArr.mbrs );
						backCArr.limit = backCArr.cap = 0;
#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM FREE( cArrToOpen.mbrs ), FREE( upCArr.mbrs )

						// If there are some candidates waiting to have open enclosing 
						// repetitions,
						if( (nofCands = cArrToOpen.limit) )
						{
							// Open them the repetitions.
							if( ! (openReps( cArrToOpen, curNode, startIdx + 1, rress )) )
							{
								FREEMEM;
								return ERRET;
							}
							// Open them parentheses, too.
							openParens( cArrToOpen, curNode->parToOpen, startIdx + 1, rress );

							// Send them up.
							if( isInvCArr( upCArr = mergeCands( &upCArr, &cArrToOpen, rress ) ) )
							{
								FREEMEM;
								return ERRET;
							}
						}
						else
						{
							FREE( cArrToOpen.mbrs );
							cArrToOpen.cap = cArrToOpen.limit = 0;
						}
#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM FREE( upCArr.mbrs )

						// If there are some candidates going up, send them up.
						if( (nofCands = upCArr.limit) )
						{
							for( candIdx = 0; candIdx < nofCands; candIdx++ )
							{
								curCand = upCArr.mbrs[ candIdx ];
								if( (hElm = curCand->hist + hIdx)->mark )
								{
									// Close this repetition.
									if( ! (disposeTR( curCand, hIdx, rress )) )
									{
										FREEMEM;
										return ERRET;
									}

									hElm->isOpen = 0;
									hElm->mark = NULL;
								}
								else
									// Close this repetition.
									curCand->hist[ hIdx ].isOpen = 0;
							}
							if( ! sendUpToNext( curNode, &upCArr, curDepth, &newDepth, 
														rress ) )
							{
								FREEMEM;
								return ERRET;
							}
						}
						else
						{
							FREE( upCArr.mbrs );
							upCArr.limit = upCArr.cap = 0;
						}

						// Dispose the candidates for disposal.
						if( ! (disposeCands( &cArrToDisp, rress )) )
							return ERRET;

						curNode->nextLCands.cap = curNode->nextLCands.limit = 0;
					}
					break;

				case or:
					if( curNode->lCands.limit | curNode->rCands.limit )
					{
						if( isInvCArr( cArr = mergeCands( &curNode->lCands,
																							&curNode->rCands, rress ) ) )
							return ERRET;
						if( ! sendUp( curNode, &cArr, curDepth, &newDepth, rress ) )
							return ERRET;
					}
					if( curNode->nextLCands.limit | curNode->nextRCands.limit )
					{
						if( isInvCArr( cArr = mergeCands( &curNode->nextLCands,
																							&curNode->nextRCands, rress ) ) )
							return ERRET;
						if( ! sendUpToNext( curNode, &cArr, curDepth, &newDepth, rress ) )
							return ERRET;
					}
					break;

				case anchor:
					switch( curNode->atom->ltrs[0] )
					{
						case L'^':
							// FIXME The new line sequence might be different from plain "\n".
							anchMatches = (startIdx == 0) ||
												(rress->text[ startIdx - 1 ] == L'\n');
							anchMatchesNext = (rress->text[ startIdx ] == L'\n');
							break;

						case L'$':
							anchMatches = (startIdx == rress->textLen) ||
														(curChar == L'\n');
							anchMatchesNext = (startIdx == rress->textLen - 1) ||
													( (startIdx < rress->textLen) &&
														(rress->text[ startIdx + 1 ] == L'\n') );
							break;

						case L'<':
							anchMatches =
										(startIdx == 0 || ! iswalnum( rress->text[ startIdx - 1] )) &&
										iswalnum( curChar );
							anchMatchesNext =
										startIdx < rress->textLen - 1 &&
										! iswalnum( curChar ) &&
										iswalnum( rress->text[ startIdx + 1 ] );
							break;

						case L'>':
							anchMatches = 
										startIdx != 0 &&
										iswalnum( rress->text[ startIdx - 1] ) &&
										! iswalnum( curChar );
							anchMatchesNext =
										iswalnum( curChar ) &&
										! iswalnum( rress->text[ startIdx + 1 ] );
							break;

						case L'b':
							anchMatches = ( ( 0 != iswalnum( curChar ) ) ==
										(startIdx == 0 || ! iswalnum( rress->text[ startIdx - 1 ] )) );
							anchMatchesNext = ( ( 0 != iswalnum( curChar ) ) ==
										(startIdx >= rress->textLen ||
										 		! iswalnum( rress->text[ startIdx + 1 ] )) );
							break;

						case L'B':
							anchMatches = ( ( 0 == iswalnum( curChar ) ) ==
										(startIdx == 0 || ! iswalnum( rress->text[ startIdx - 1 ] )) );
							anchMatchesNext = ( ( 0 == iswalnum( curChar ) ) ==
										(startIdx >= rress->textLen ||
										 		! iswalnum( rress->text[ startIdx + 1 ] )) );
							break;

#ifdef DEBUG
						default:
							assert( 0 );
#endif
					}
					if( curNode->lCands.limit )
					{
						if( anchMatches )
						{
							if( ! (openReps( curNode->lCands,
												curNode->startedRep, startIdx, rress )) )
								return ERRET;
							openParens( curNode->lCands, curNode->parToOpen, startIdx, rress );

							if( ! sendUp( curNode, &curNode->lCands, curDepth, &newDepth, 
											rress ) )
								return ERRET;
						}
						else
							if( ! disposeCands( &curNode->lCands, rress ) )
								return ERRET;
					}
					if( curNode->nextLCands.limit )
					{
						if( anchMatchesNext )
						{
							if( ! (openReps( curNode->nextLCands,
												curNode->startedRep, startIdx, rress )) )
								return ERRET;
							openParens( curNode->nextLCands, curNode->parToOpen, startIdx, rress );

							if( ! sendUpToNext( curNode, &curNode->nextLCands,
														curDepth, &newDepth, rress ) )
								return ERRET;
						}
						else
							if( ! disposeCands( &curNode->nextLCands, rress ) )
								return ERRET;
					}
					break;
			}
#ifdef DEBUG
					assert( 1 == checkNofLinks( rress ) );
#endif
			// If it is a starting node, schedule it to become active the next time.
			if( curNode->isStartNode && !curNode->isNActive )
			{
				curNode->isNActive = 1;
				curNode->nextNAct = rress->nextActNodes[ curDepth ];
				rress->nextActNodes[ curDepth ] = curNode;
			}
			// Depth might have been reset.
			if( newDepth > curDepth )
				break;
		}
	}
	
	// Return candidates that have reached the root.
		updNode( rress->tree, startIdx );
		backCArr = rress->tree->lCands;
		rress->tree->lCands.cap = rress->tree->lCands.limit = 0;

		// Update `end's of all candidates to be returned.
		origCands = backCArr.mbrs;
		for( candIdx = backCArr.limit - 1;
					candIdx != (unsigned int) -1;
					candIdx-- )
			origCands[ candIdx ]->end = startIdx;
	if( rress->bestCands )
		detach( &backCArr, rress );
	return backCArr;
}

/**
 * Updates the node if it has not been touched yet when processing the text at 
 * the point `tIdx'.
 */
static inline void updNode( node* node, t_idx tIdx )
{
	if( node->lastTIdx < tIdx )
	{
		node->lCands = node->nextLCands;
		node->nextLCands.cap = node->nextLCands.limit = 0;
		node->rCands = node->nextRCands;
		node->nextRCands.cap = node->nextRCands.limit = 0;
		node->lastTIdx = tIdx;
	}
}

/**
 * Sends given array of candidates from given node to its parent node.
 *
 * Arguments:
 * 	curNode		: the node to whose parent node the array is to be sent
 * 	inCArr		: the array of candidates (will be emptied)
 * 	curDepth	: currently processed depth
 * 	newDepth	: new depth to be processed
 * 	rress			: regex resources
 *
 * Returns 1 iff the operation was successful.
 * Returns 0 iff not enough memory was available for allocation.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET 0
static inline _Bool sendUp( node *curNode, candArr *inCArr,
										r_idx curDepth, r_idx *newDepth, rxAnaRess *rress )
{
	candArr cArrCopy, *wCArr;
	node *adNode;
	t_idx startIdx = rress->nextTIdx;

#ifdef DEBUG
	assert( !( curNode->up->adjoined && curNode->up->op == rep )	||
					rress->repProps[ rress->repPriors[ curNode->up->lrOrder ] ].minReps == 0 );
#endif

	_Bool resend = ( curNode->up->adjoined &&
										!( isOpeningPar( curNode->up ) && curNode->isRight ) &&
										( curNode->up->op != rep ) );

	if( resend )
	{
		if( isInvCArr( cArrCopy = cloneCArr( *inCArr, rress ) ) )
			return ERRET;

		wCArr = &cArrCopy;
	}
	else
		wCArr = inCArr;

	updNode( curNode->up, startIdx );
	if( curNode->isRight )
	{
		if( isInvCArr( curNode->up->rCands =
						mergeCands( &curNode->up->rCands, wCArr, rress ) ) )
			return ERRET;
	}
	else
	{
		if( isInvCArr( curNode->up->lCands =
						mergeCands( &curNode->up->lCands, wCArr, rress ) ) )
			return ERRET;
	}

	if( !curNode->up->isActive )
	{
		curNode->up->isActive = 1;
		curNode->up->nextAct = rress->actNodes[ curDepth - 1 ];
		rress->actNodes[ curDepth - 1 ] = curNode->up;
	}
	if( resend )
	{
		unsigned int candIdx, nofCands = inCArr->limit;
		for( adNode = curNode->up->adjoined; adNode != NULL; adNode = adNode->adjoined )
		{
			// Copy the input array and merged it to the destination array.
			if( isInvCArr( cArrCopy = cloneCArr( *inCArr, rress ) ) )
				return ERRET;
			// Open parentheses for the candidates.
			openParens( cArrCopy, adNode->parToOpen, rress->nextTIdx, rress );

			updNode( adNode, startIdx );
			if( isInvCArr( adNode->lCands =
							mergeCands( &adNode->lCands, &cArrCopy, rress ) ) )
				return ERRET;

			if( !adNode->isActive )
			{
				adNode->isActive = 1;
				adNode->nextAct = rress->actNodes[ adNode->depth ];
				rress->actNodes[ adNode->depth ] = adNode;
			}
			*newDepth = *newDepth > adNode->depth ? *newDepth : adNode->depth;
		}
		if( ! disposeCands( inCArr, rress ) )
			return ERRET;
	}

	return 1;
}

/**
 * Sends given array of candidates from given node to its parent node, to the 
 * `next_' array of candidates.
 *
 * Arguments:
 * 	curNode		: the node to whose parent node the array is to be sent
 * 	inCArr		: the array of candidates (will be emptied)
 * 	curDepth	: currently processed depth
 * 	newDepth	: new depth to be processed
 * 	rress			: regex resources
 *
 * Returns 1 iff the operation was successful.
 * Returns 0 iff not enough memory was available to allocate.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET 0
static inline _Bool sendUpToNext( node *curNode, candArr *inCArr,
										r_idx curDepth, r_idx *newDepth, rxAnaRess *rress )
{
	candArr cArrCopy, *wCArr;
	node *adNode;
	t_idx startIdx = rress->nextTIdx;

#ifdef DEBUG
	assert( !( curNode->up->adjoined && curNode->up->op == rep )	||
					rress->repProps[ rress->repPriors[ curNode->up->lrOrder ] ].minReps == 0 );
#endif

	_Bool resend = ( curNode->up->adjoined &&
										!( isOpeningPar( curNode->up ) && curNode->isRight ) &&
										( curNode->up->op != rep ) );

	if( resend )
	{
		if( isInvCArr( cArrCopy = cloneCArr( *inCArr, rress ) ) )
			return ERRET;

		wCArr = &cArrCopy;
	}
	else
		wCArr = inCArr;

	updNode( curNode->up, startIdx );
	if( curNode->isRight )
	{
		if( isInvCArr( curNode->up->nextRCands =
						mergeCands( &curNode->up->nextRCands, wCArr, rress ) ) )
			return ERRET;
	}
	else
	{
		if( isInvCArr( curNode->up->nextLCands =
						mergeCands( &curNode->up->nextLCands, wCArr, rress ) ) )
			return ERRET;
	}

	if( !curNode->up->isActive )
	{
		curNode->up->isActive = 1;
		curNode->up->nextAct = rress->actNodes[ curDepth - 1 ];
		rress->actNodes[ curDepth - 1 ] = curNode->up;
	}
	if( resend )
	{
		/* node with '(' which becomes open for the candidates */
		node *parToOpen;

		unsigned int candIdx, nofCands = inCArr->limit;
		for( adNode = curNode->up->adjoined; adNode != NULL; adNode = adNode->adjoined )
		{
			// Copy the input array and merged it to the destination array.
			if( isInvCArr( cArrCopy = cloneCArr( *inCArr, rress ) ) )
				return ERRET;
			// Open parentheses for the candidates.
			openParens( cArrCopy, adNode->parToOpen, rress->nextTIdx, rress );

			updNode( adNode, startIdx );
			if( isInvCArr( adNode->nextLCands =
							mergeCands( &adNode->nextLCands, &cArrCopy, rress ) ) )
				return ERRET;
			
			if( !adNode->isActive )
			{
				adNode->isActive = 1;
				adNode->nextAct = rress->actNodes[ adNode->depth ];
				rress->actNodes[ adNode->depth ] = adNode;
			}
			*newDepth = *newDepth > adNode->depth ? *newDepth : adNode->depth;
		}
		if( ! disposeCands( inCArr, rress ) )
			return ERRET;
	}

	return 1;
}

/**
 * Frees all memory allocated for analyzing a text with given regex.
 *
 * Returns 1 iff the operation was successful.
 * Returns 0 iff not enough memory was available to allocate.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET 0
inline _Bool cleanRress( rxAnaRess *rress )
{
#ifdef DEBUG
	assert( !rress->isClean );
#endif

	r_idx nodeIdx;
	node *curNode;
	r_idx curDepth;
	
	// Dispose all information about active and next active nodes.
	memset( rress->actNodes, 0, (rress->depth + 1) * sizeof( node** ) );
	memset( rress->nextActNodes, 0, (rress->depth + 1) * sizeof( node** ) );

	// Dispose all candidates in the regex tree.
	for( nodeIdx = rress->nofNodes - 1; nodeIdx != negRIdx; nodeIdx-- )
	{
		curNode = &rress->allocNodes[ nodeIdx ];
		// FIXME (enhancement) Dispose the candidates without keeping any more 
		// invariants, like `repMark's' `nofLinks'.
		if( curNode->lCands.cap )
			if( ! disposeCands( &curNode->lCands, rress ) )
				return ERRET;

		if( curNode->nextLCands.cap )
			if( ! disposeCands( &curNode->nextLCands, rress ) )
				return ERRET;

		if( curNode->rCands.cap )
			if( ! disposeCands( &curNode->rCands, rress ) )
				return ERRET;

		if( curNode->nextRCands.cap )
			if( ! disposeCands( &curNode->nextRCands, rress ) )
				return ERRET;

		// Initialize information about starting nodes.
		if( curNode->isStartNode )
		{
			curNode->nextNAct = rress->nextActNodes[ curNode->depth ];
			rress->nextActNodes[ curNode->depth ] = curNode;
			curNode->isNActive = 1;
		}
		else
			curNode->isNActive = 0;
		curNode->isActive = 0;
	}

	// Dispose all best candidates and related resources.
	if( rress->bestCands )
	{
		t_idx tIdx;
		cand_l *curCand_elm, *prevCand_elm;
		for( tIdx = rress->textLen; tIdx != negTIdx; tIdx-- )
		{
			prevCand_elm = rress->bestCands[ tIdx ].matchingCands;
			while( prevCand_elm )
			{
				curCand_elm = prevCand_elm->next;
				disposeFreeCand( prevCand_elm->val, rress );
				FREE( prevCand_elm );
				prevCand_elm = curCand_elm;
			}
		}
		FREE( rress->bestCands );
		rress->bestCands = NULL;
	}

	// Forget about the text analyzed.
	rress->text = NULL;
	rress->textLen = 0;
	rress->nextTIdx = 0;

#ifdef DEBUG
	assert( *rress->marksTree == NULL );
#endif
	rress->isClean = 1;

	return 1;
}

/**
 * Frees all memory allocated for compiling a regex and analyzing a text using 
 * it.
 *
 * Returns 1 iff the operation was successful.
 * Returns 0 iff not enough memory was available to allocate.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET 0
inline _Bool freeRress( rxAnaRess *rress )
{
	if( !rress->isClean )
		if( ! cleanRress( rress ) )
			return ERRET;

	FREE( rress->allocNodes );
	FREE( rress->allocAtoms );
	FREE( rress->allocLtrs );
	FREE( rress->allocProps );

	FREE( rress->actNodes );
	FREE( rress->nextActNodes );

	FREE( rress->repProps );
	FREE( rress->repPriors );

	FREE( rress->initParens );

#ifdef DEBUG
	assert( *rress->marksTree == NULL );
#endif
	FREE( rress->marksTree );

	return 1;
}

/**
 * Clones an array of candidates, updating all related invariants, including 
 * text references.
 *
 * Returns the copied array.
 *
 * In case of exception, returns an array of candidates equal to `excCArr'.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET excCArr
static inline candArr cloneCArr( candArr inCArr, rxAnaRess *rress )
{
	candArr outCArr;
	cand *origCand, *newCand;
	unsigned int candIdx;
	h_idx hIdx;

	SMALLOC( outCArr.mbrs,
					 (outCArr.cap = outCArr.limit = inCArr.limit),
					 cand* )
	outCArr.isFree = inCArr.isFree;
	// Copy all the candidates with their histories.
	for( candIdx = inCArr.limit - 1;
					candIdx != (unsigned int) -1;
					candIdx-- )
	{
		origCand = inCArr.mbrs[ candIdx ];
		SMALLOC( newCand, 1, cand )
		if( rress->nofReps )
		{
			SMALLOC( newCand->hist, rress->nofReps, h_elm )
			memcpy( newCand->hist,
									origCand->hist,
									rress->nofReps * sizeof( h_elm ) );
			for( hIdx = rress->nofReps - 1; hIdx != negHIdx; hIdx-- )
			{
				if( origCand->hist[ hIdx ].mark )
					origCand->hist[ hIdx ].mark->nofLinks++;
			}
		}
		if( rress->nofParens )
		{
			SMALLOC( newCand->parens, rress->nofParens, begend )
			memcpy( newCand->parens,
									origCand->parens,
									rress->nofParens * sizeof( begend ) );
		}
		newCand->start = origCand->start;
		if( rress->bestCands )
			rress->bestCands[ origCand->start ].nofCandsInTree++;
		outCArr.mbrs[ candIdx ] = newCand;
	}

	return outCArr;
}

/**
 * Opens all parentheses starting in the given node.
 *
 * Arguments:
 * 	parToOpen	: first enclosing parentheses' node
 * 	cands			: the candidates that start the parenthesized span here
 * 	where			: the text index where the parenthesized span actually starts
 * 	rress			: regex analysis resources
 */
static inline void openParens( const candArr cands, const node *parToOpen,
															 const t_idx where, const rxAnaRess *const rress )
{
	unsigned int candIdx;
	while( parToOpen != NULL )
	{
		if( parToOpen->lrOrder < MAX_DIFF_REFS )
		{
			for( candIdx = cands.limit - 1;
								candIdx != (unsigned int) -1;
								candIdx-- )
				cands.mbrs[ candIdx ]->parens[ parToOpen->lrOrder - 1 ].begin = where;
		}
		parToOpen = parToOpen->parToOpen;
	}
}

/**
 * Opens all repetitions starting in the given node.
 *
 * Arguments:
 * 	cands			: array of candidates to have repetitions open
 * 	encNode		: the tightliest enclosing node of a repetition operator
 * 	startIdx	: index for start of the repetitions that become newly open
 * 	rress			: regex analysis resources
 *
 * Returns 1 iff the operation was successful.
 * Returns 0 iff not enough memory was available to allocate.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET 0
static inline _Bool openReps( const candArr cands, const node *encNode,
															const t_idx startIdx, rxAnaRess *const rress )
{
	h_idx hIdx, encHIdx;
	h_elm *hElm;
	unsigned int candIdx;
	cand *curCand;
	node *encEncNode;

	// This function does anything only for nodes opening a repetition.
	if( !encNode )
		return 1;

	_Bool isReady[ cands.limit ];
	memset( isReady, 0, cands.limit * sizeof( _Bool ) );

	/* history index of the current repetition operator */
	hIdx = rress->repPriors[ encNode->lrOrder ];
	// Open all higher-order repetitions.
	for( ;
				(encEncNode = encNode->startedRep) != NULL;
				encNode = encEncNode, hIdx = encHIdx )
	{
		/* history index of the enclosing repetition operator */
		encHIdx = rress->repPriors[ encEncNode->lrOrder ];
		for( candIdx = cands.limit - 1;
					candIdx != (unsigned int) -1;
					candIdx-- )
		{
			curCand = cands.mbrs[ candIdx ];
			if( isReady[ candIdx ] ||
					(hElm = curCand->hist + hIdx)->isOpen )
			{
				isReady[ candIdx ] = 1;
				continue;
			}
			hElm->unbounded = hElm->repCnt = 0;
			hElm->isOpen = hElm->used = 1;
			if( ! (hElm->mark = addRepMark( startIdx, hIdx, curCand->start,
																			startIdx, encHIdx, rress )) )
				return ERRET;

			hElm->start = startIdx;
		}
	}
	// Open the outermost repetition.
	for( candIdx = cands.limit - 1;
				candIdx != (unsigned int) -1;
				candIdx-- )
	{
		if( isReady[ candIdx ] ||
				(hElm = cands.mbrs[ candIdx ]->hist + hIdx)->isOpen )
			continue;
		hElm->unbounded = hElm->repCnt = 0;
		hElm->isOpen = hElm->used = 1;
		hElm->start = startIdx;
	}
	return 1;
}

/**
 * Merges two properly ordered sets of candidates into one and disposes 
 * resources used by the original sets.
 *
 * Arguments:
 * 		arr1, arr2	: sets of candidates to be merged
 * 		rress				: current regex resources
 *
 * Returns the merged array of candidates.
 *
 * In case of exception, returns an array equal to `excCArr'.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET excCArr
static inline candArr mergeCands( candArr* arr1, candArr* arr2,
																	rxAnaRess *rress )
{
	candArr merged;	// the future return value
	if( arr1->limit == 0 )
	{
		merged = *arr2;
		arr2->cap = arr2->limit = 0;
		if( arr1->cap )
		{
			FREE( arr1->mbrs );
			arr1->cap = 0;
		}
	}
	else if( arr2->limit == 0 )
	{
		merged = *arr1;
		arr1->cap = arr1->limit = 0;
		if( arr2->cap )
		{
			FREE( arr2->mbrs );
			arr2->cap = 0;
		}
	}
	else
	{
		merged.limit = 0;
		SMALLOC( merged.mbrs, 
						 (merged.cap = (arr1->limit + arr2->limit)),
						 cand* )
#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM FREE( merged.mbrs )

		merged.isFree = arr1->isFree;

		unsigned int cand1Idx = 0, cand2Idx = 0, candIdx = 0;
		cand *cand1, *cand2;
		int comparison;
		do
		{
			comparison = compCands( cand1 = arr1->mbrs[ cand1Idx ],
															cand2 = arr2->mbrs[ cand2Idx ],
															rress );
			switch( comparison )
			{
				case 7:
				case 2:
					// Dispose the losing candidate.
					if( ! (disposeCand( cand2, rress )) )
					{
						FREEMEM;
						return ERRET;
					}
					// Advance to the next one.
					cand2Idx++;
				case 1:
				case 0:
					// Save the winner in the merged array.
					merged.mbrs[ candIdx++ ] = cand1;
					cand1Idx++;
					break;
				case -2:
					// Dispose the losing candidate.
					if( ! (disposeCand( cand1, rress )) )
					{
						FREEMEM;
						return ERRET;
					}
					// Advance to the next one.
					cand1Idx++;
				case -1:
					// Save the winner into the merged array.
					merged.mbrs[ candIdx++ ] = cand2;
					cand2Idx++;
			}
		} while( cand1Idx < arr1->limit && cand2Idx < arr2->limit );

		if( cand1Idx < arr1->limit )
		{
			memcpy( merged.mbrs + candIdx,
									arr1->mbrs + cand1Idx,
									(arr1->limit - cand1Idx) * sizeof( cand* ) );
			merged.limit = candIdx + arr1->limit - cand1Idx;
		}
		else if( cand2Idx < arr2->limit )
		{
			memcpy( merged.mbrs + candIdx,
									arr2->mbrs + cand2Idx,
									(arr2->limit - cand2Idx) * sizeof( cand* ) );
			merged.limit = candIdx + arr2->limit - cand2Idx;
		}
		else
			merged.limit = candIdx;

		if( arr1->cap )
		{
			FREE( arr1->mbrs );
			arr1->limit = arr1->cap = 0;
		}
		if( arr2->cap )
		{
			FREE( arr2->mbrs );
			arr2->limit = arr2->cap = 0;
		}
	}
	return merged;
}

/**
 * Detaches a candidates array from the regex tree.
 *
 * Arguments:
 * 	cArr	: the candidates array to detach
 * 	rress	:	regex analysis resources
 */
static inline void detach( candArr *cArr, rxAnaRess *rress )
{
#ifdef DEBUG
	assert( ! cArr->isFree );
#endif
	unsigned int candIdx;

	for( candIdx = cArr->limit - 1; candIdx != (unsigned int) -1; candIdx-- )
		--rress->bestCands[ cArr->mbrs[ candIdx ]->start ].nofCandsInTree;

	cArr->isFree = 1;
}

/**
 * Disposes a single candidate including all resources allocated for it.
 *
 * Returns 1 iff the operation was successful.
 * Returns 0 iff not enough memory was available to allocate.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET 0
static inline _Bool disposeCand( cand *cand, rxAnaRess *rress )
{
	h_idx hIdx;
	for( hIdx = rress->nofReps - 1; hIdx != negHIdx; hIdx-- )
		if( cand->hist[ hIdx ].mark )
			if( ! (disposeTR( cand, hIdx, rress )) )
				return ERRET;

	if( rress->bestCands )
		rress->bestCands[ cand->start ].nofCandsInTree--;

	if( rress->nofReps )
		FREE( cand->hist );
	if( rress->nofParens )
		FREE( cand->parens );
	FREE( cand );

	return 1;
}

/**
 * Disposes a single free candidate.
 */
static inline void disposeFreeCand( cand *cand, rxAnaRess *rress )
{
	if( rress->nofReps )
		FREE( cand->hist );
	if( rress->nofParens )
		FREE( cand->parens );
	FREE( cand );
}

/**
 * Disposes an array of candidates including all resources allocated for it.
 *
 * Returns 1 iff the operation was successful.
 * Returns 0 iff not enough memory was available to allocate.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET 0
static inline _Bool disposeCands( candArr *cands, rxAnaRess *rress )
{
	unsigned int candIdx;
	for( candIdx = cands->limit - 1;
					candIdx != (unsigned int) -1;
					candIdx-- )
		if( ! (disposeCand( cands->mbrs[ candIdx ], rress )) )
			return ERRET;

	FREE( cands->mbrs );
	cands->cap = cands->limit = 0;

	return 1;
}

/**
 * Disposes candidates with specified starts.
 *
 * Arguments:
 * 	maxStart	: the maximal start index for candidates to dispose
 * 	rress			: the resources for the given regex and text
 *
 * Returns 1 iff the operation was successful.
 * Returns 0 iff not enough memory was available to allocate.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET 0
static inline _Bool disposeEarlyCands( const t_idx maxStart, rxAnaRess *const rress )
{
#ifdef DEBUG
	assert( !rress->isClean );
#endif

	r_idx nodeIdx;
	node *curNode;
	
	// Dispose all candidates in the regex tree.
	for( nodeIdx = rress->nofNodes - 1; nodeIdx != negRIdx; nodeIdx-- )
	{
		curNode = &rress->allocNodes[ nodeIdx ];
		
		if( curNode->lCands.cap )
		{
			if( ! disposeEarlyCandsSub( maxStart, &curNode->lCands, rress ) )
				return ERRET;
		}
		if( curNode->nextLCands.cap )
		{
			if( ! disposeEarlyCandsSub( maxStart, &curNode->nextLCands, rress ) )
				return ERRET;
		}
		if( curNode->rCands.cap )
		{
			if( ! disposeEarlyCandsSub( maxStart, &curNode->rCands, rress ) )
				return ERRET;
		}
		if( curNode->nextRCands.cap )
		{
			if( ! disposeEarlyCandsSub( maxStart, &curNode->nextRCands, rress ) )
				return ERRET;
		}
	}

	// Dispose small best candidates and related resources.
	if( rress->bestCands )
	{
		t_idx tIdx;
		cand_l *curCand_elm, *prevCand_elm;
		for( tIdx = rress->firstStart;
					tIdx <= maxStart;
					tIdx++ )
		{
			prevCand_elm = rress->bestCands[ tIdx ].matchingCands;
			while( prevCand_elm )
			{
				curCand_elm = prevCand_elm->next;
				disposeFreeCand( prevCand_elm->val, rress );
				FREE( prevCand_elm );
				prevCand_elm = curCand_elm;
			}
			rress->bestCands[ tIdx ].matchingCands = NULL;
		}
		if( rress->firstStart <= maxStart )
			rress->firstStart = maxStart + 1;
	}

	return 1;
}

/**
 * Disposes candidates with specified starts from the specified candidates 
 * array.
 *
 * Arguments:
 * 	maxStart	: the maximal start index for candidates to dispose
 * 	cArr			: the candidates array to dispose candidates from
 * 	rress			: the resources for the given regex and text
 *
 * Returns 1 iff the operation was successful.
 * Returns 0 iff not enough memory was available to allocate.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET 0
static inline _Bool disposeEarlyCandsSub( const t_idx maxStart,
			candArr *const cArr, rxAnaRess *const rress )
{
	unsigned int candIdx;
	unsigned int deleted = 0;
	unsigned int nofCands = cArr->limit;
	cand *curCand;

	for( candIdx = 0; candIdx < nofCands; candIdx++ )
	{
		curCand = cArr->mbrs[ candIdx ];
		if( curCand->start > maxStart )
			break;
		else
		{
			if( ! disposeCand( curCand, rress ) )
				return ERRET;
			deleted++;
		}
	}
	// If any candidates were deleted.
	// Update current number of candidates.
	if( deleted && (cArr->limit -= deleted) )
		// Shift the tail of the array forwards.
		memmove( cArr->mbrs, cArr->mbrs + deleted, cArr->limit * sizeof( cand* ) );

	return 1;
}

/**
 * Disposes resources bound by given text reference by given referring 
 * candidate. Assumes that the implied repetition mark exists in `marksTree'.
 *
 * Returns 1 iff the operation was successful.
 * Returns 0 iff not enough memory was available to allocate.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET 0
static inline _Bool disposeTR( cand *referee, h_idx repPrior, rxAnaRess *rress )
{
	repMark *curMark;
	int markIdx;
	repMark_l *marksToRemove, *markLMbr;

	// Put the reference in a list as the first mark possibly to be removed.
	SMALLOC( marksToRemove, 1, repMark_l )
	marksToRemove->val = referee->hist[ repPrior ].mark;
	marksToRemove->next = NULL;
	while( marksToRemove && (curMark = marksToRemove->val) )
	{
		// Free memory allocated for this list member.
		markLMbr = marksToRemove;
		marksToRemove = marksToRemove->next;
		FREE( markLMbr );
		// Subtract from number of links to the mark; if it is zero, remove the 
		// mark.
		if( ! --(curMark->nofLinks) )
		{
			if( curMark->nofMarks )
			{
				// Schedule all the marks linked from here for removal (of the link).
				for( markIdx = curMark->nofMarks - 1;
								markIdx >= 0;
								markIdx-- )
				{
					SMALLOC( markLMbr, 1, repMark_l )
					markLMbr->val = curMark->repStart[ markIdx ];
					markLMbr->next = marksToRemove;
					marksToRemove = markLMbr;
				}
				FREE( curMark->repStart );
				FREE( curMark->repCnt );
			}
			tdelete( curMark, rress->marksTree, compMarkKeys );
			FREE( curMark );
		}
	}
	return 1;
}

/**
 * Finds the best among repetition counts for a mark. If there is such a count, 
 * at least `minReps', the return value is at least `minReps'. If there is such 
 * a count, at most `maxReps', the return value is at most `maxReps'. Whether 
 * the minimal, or maximal one of possible values is returned, is determined by the 
 * value of `isGreedy'.
 */
static inline unsigned int getBestRepCnt( repMark *mark,
			unsigned int minReps, unsigned int maxReps, _Bool isGreedy )
{
	unsigned int nofMarks, markIdx;
	if( (nofMarks = mark->nofMarks) )
	{
		if( isGreedy )
		{
			for( markIdx = nofMarks - 1; markIdx != (unsigned int) -1; markIdx-- )
			{
				if( mark->repCnt[ markIdx ] <= maxReps )
					return mark->repCnt[ markIdx ];
			}
			return mark->repCnt[0];
		}
		else
		{
			for( markIdx = 0; markIdx < nofMarks; markIdx++ )
			{
				if( mark->repCnt[ markIdx ] >= minReps )
					return mark->repCnt[ markIdx ];
			}
			return mark->repCnt[ nofMarks - 1 ];
		}
	}
	return 0;
}

/**
 * Adds a repetition mark to given position.
 *
 * Arguments:
 * 		tIdx					:	text index to where the repetition's instance is starting
 * 		repPrior			: index of the repetition
 * 		start					: start of candidates the mark shall apply to
 * 		prevTIdx			:	text index to where the previous repetition's instance 
 * 										started; if this is the first repetition, this argument 
 * 										should contain the value of `negTIdx'
 * 		prevRepPrior	: index of the previous repetition (equal to `repPrior', or 
 * 										index of the enclosing rep.)
 *
 * Returns a pointer to the required mark iff the operation was successful.
 * Returns NULL iff not enough memory was available to allocate.
 */
#ifdef ERRET
#undef ERRET
#endif
#define ERRET NULL
static inline repMark *addRepMark( t_idx tIdx, h_idx repPrior, t_idx start,
			t_idx prevTIdx, h_idx prevRepPrior, rxAnaRess *rress )
{
	unsigned int maxReps = rress->repProps[ repPrior ].maxReps;
	repMark *newMark, *prevMark;
	repMark *exNewMark, *exPrevMark;
	int optIdx, newOptIdx;
	// Initialize key for the new mark with given parameters.
	SMALLOC( newMark, 1, repMark )
	newMark->tIdx = tIdx;
	newMark->repPrior = repPrior;
	newMark->start = start;
	// Initialize key for the previous mark with given parameters.
	SMALLOC( prevMark, 1, repMark )
	prevMark->tIdx = prevTIdx;
	prevMark->repPrior = prevRepPrior;
	prevMark->start = start;
#ifdef FREEMEM
#undef FREEMEM
#endif
#define FREEMEM FREE( prevMark ), FREE( newMark )

	// Look up `key' in the marks tree.
		// If it is newly added there,
	if( newMark == ( exNewMark = *(repMark**) tsearch( newMark, rress->marksTree, compMarkKeys ) ) )
	{
		// Finish creating the mark.
				// Create it if it did not exist.
			if( prevMark == ( exPrevMark = *(repMark**) tsearch( prevMark, rress->marksTree, compMarkKeys ) ) )
			{
#ifdef DEBUG
				assert( repPrior != prevRepPrior );
#endif
				prevMark->nofLinks = prevMark->nofMarks = prevMark->unbounded = 0;
			}
			else
				FREE( prevMark );
			// Catch an exception -- no space.
			if( ! exPrevMark )
			{
				FREEMEM;
				return ERRET;
			}
			// Link to it and update the repetition count.
				// Either the previous mark was for the same repetition op,
			if( repPrior == prevRepPrior )
			{
					// Copy all rep. counts, increased by one.
				newMark->unbounded = exPrevMark->unbounded;
				if( (newMark->nofMarks = exPrevMark->nofMarks) )
				{
					SMALLOC( newMark->repStart, exPrevMark->nofMarks, repMark* )
					SMALLOC( newMark->repCnt, exPrevMark->nofMarks, unsigned short )
					memcpy( newMark->repStart, exPrevMark->repStart, 
									exPrevMark->nofMarks * sizeof( repMark* ) );
					memcpy( newMark->repCnt, exPrevMark->repCnt, 
									exPrevMark->nofMarks * sizeof( unsigned int ) );
					for( optIdx = newMark->nofMarks - 1; optIdx >= 0; optIdx-- )
					{
						if( newMark->repCnt[ optIdx ]++ > maxReps )
							newMark->nofMarks--;
						else
							newMark->repStart[ optIdx ]->nofLinks++;
					}
					if( !newMark->nofMarks )
					{
						FREE( newMark->repStart );
						FREE( newMark->repCnt );
					}
				}
			}
				// Or, the previous mark was for an enclosing repetition,
			else
			{
					// Note down that this is the first repetition instance.
				SMALLOC( newMark->repStart, 1, repMark* )
				*newMark->repStart = exPrevMark;
				exPrevMark->nofLinks++;
				SMALLOC( newMark->repCnt, 1, unsigned short )
				*newMark->repCnt = 0;
				newMark->nofMarks = 1;
				newMark->unbounded = 0;
			}
		newMark->nofLinks = 1;
		return newMark;

	}
		// Or, if a corresponding mark was in the tree already,
	else
	{
#ifdef DEBUG
		assert( prevTIdx != negTIdx );
#endif
		// Catch an exception -- no space.
		if( ! exNewMark )
		{
			FREEMEM;
			return ERRET;
		}
		// Find whether the supposed previous mark is already pointed to from here.
		for( optIdx = exNewMark->nofMarks - 1; optIdx >= 0; optIdx-- )
		{
			exPrevMark = exNewMark->repStart[ optIdx ];
			if( exPrevMark->tIdx == prevTIdx &&
					exPrevMark->repPrior == prevRepPrior )
			{
#ifdef DEBUG
				assert( exNewMark->unbounded == exPrevMark->unbounded );
#endif
				break;
			}
		}
		// If the mark is not yet pointed to,
		if( optIdx < 0 )
		{
			// Create the previous mark if it did not exist.
			if( prevMark == ( exPrevMark = *(repMark**) tsearch( prevMark, rress->marksTree, compMarkKeys ) ) )
			{
#ifdef DEBUG
				assert( repPrior != prevRepPrior );
#endif
				prevMark->nofLinks = prevMark->nofMarks = prevMark->unbounded = 0;
			}
			else
				FREE( prevMark );
			// Catch an exception -- no space.
			if( ! exPrevMark )
			{
				FREEMEM;
				return ERRET;
			}
			// Add links to it for rep. counts not yet present here.
			unsigned int newNofMarks = 0;
			if( prevRepPrior == repPrior )
			{
				// Special case: a mark referring to itself.
				if( exNewMark == exPrevMark )
				{
					exNewMark->unbounded = 1;
				}
				else
				{
					// Count the number of new links.
					unsigned short prevCnt, thisCnt;
					int prevOptIdx;
					for( prevOptIdx = exPrevMark->nofMarks - 1, optIdx = exNewMark->nofMarks - 1;
										prevOptIdx >= 0 && optIdx >= 0;
										prevOptIdx-- )
					{
						prevCnt = exPrevMark->repCnt[ prevOptIdx ];
						while( optIdx >= 0 && exNewMark->repCnt[ optIdx ] > prevCnt )
							optIdx--;
						newNofMarks += ( optIdx < 0 || exNewMark->repCnt[ optIdx ] < prevCnt );
					}
					newNofMarks += prevOptIdx + 1;
					// Create new arrays of links and of counts.
					newNofMarks += exNewMark->nofMarks;
					*newMark = *exNewMark;
					newMark->nofMarks = newNofMarks;
					SMALLOC( newMark->repCnt, newNofMarks, unsigned short )
					SMALLOC( newMark->repStart, newNofMarks, repMark* )
	
					prevOptIdx = exPrevMark->nofMarks - 1;
					optIdx = exNewMark->nofMarks - 1;
					newOptIdx = newNofMarks - 1;
					prevCnt = exPrevMark->repCnt[ prevOptIdx ];
					thisCnt = exNewMark->repCnt[ optIdx ];
					// Merge the previous and existing mark's arrays.
					while( 1 )
					{
						if( prevCnt > thisCnt )
						{
							newMark->repStart[ newOptIdx ] = exPrevMark->repStart[ prevOptIdx ];
							newMark->repStart[ newOptIdx ]->nofLinks++;
							newMark->repCnt[ newOptIdx-- ] = prevCnt;
							if( ! prevOptIdx-- )
								break;
							else
								prevCnt = exPrevMark->repCnt[ prevOptIdx ];
						}
						else if( prevCnt < thisCnt )
						{
							newMark->repStart[ newOptIdx ] = exNewMark->repStart[ optIdx ];
							newMark->repCnt[ newOptIdx-- ] = thisCnt;
							if( ! optIdx-- )
								break;
							else
								thisCnt = exNewMark->repCnt[ optIdx ];
						}
						else
						{
							newMark->repStart[ newOptIdx ] = exNewMark->repStart[ optIdx ];
							newMark->repCnt[ newOptIdx-- ] = thisCnt;
							if( (! optIdx--) | (! prevOptIdx--) )
								break;
							else
							{
								thisCnt = exNewMark->repCnt[ optIdx ];
								prevCnt = exPrevMark->repCnt[ prevOptIdx ];
							}
						}
					}
					while( optIdx >= 0 )
					{
						newMark->repStart[ newOptIdx ] = exNewMark->repStart[ optIdx ];
						newMark->repCnt[ newOptIdx-- ] = exNewMark->repCnt[ optIdx-- ];
					}
					while( prevOptIdx >= 0 )
					{
						newMark->repStart[ newOptIdx ] = exPrevMark->repStart[ prevOptIdx ];
						newMark->repStart[ newOptIdx ]->nofLinks++;
						newMark->repCnt[ newOptIdx-- ] = exPrevMark->repCnt[ prevOptIdx-- ];
					}
					// Substitute the new mark for the existing one.
#ifdef DEBUG
					assert( exNewMark->nofMarks );
#endif
					FREE( exNewMark->repCnt );
					FREE( exNewMark->repStart );
					*exNewMark = *newMark;
					exNewMark->unbounded |= exPrevMark->unbounded;
				}
			}	// end if( prevRepPrior == repPrior )
			else
			{
#ifdef DEBUG
				// If it is not already linked,
				if( ! exNewMark->nofMarks ||
						exNewMark->repStart[0] != exPrevMark )
				{
#endif
					// Link to the enclosing rep. mark. (Shift it in to the arrays 
					// `repCnt' and `repStart').
					*newMark = *exNewMark;
					SMALLOC( newMark->repCnt, ++newMark->nofMarks, unsigned short )
					*newMark->repCnt = 0;
					SMALLOC( newMark->repStart, newMark->nofMarks, repMark* )
					*newMark->repStart = exPrevMark;
					exPrevMark->nofLinks++;

					if( exNewMark->nofMarks )
					{
						memcpy( newMark->repCnt + 1,
										exNewMark->repCnt,
										exNewMark->nofMarks * sizeof( unsigned short ) );
						memcpy( newMark->repStart + 1,
										exNewMark->repStart,
										exNewMark->nofMarks * sizeof( repMark* ) );
						// Substitute the new mark for the existing one.
						FREE( exNewMark->repCnt );
						FREE( exNewMark->repStart );
					}
					*exNewMark = *newMark;
#ifdef DEBUG
				}
				else assert( 1 == 0 );
#endif
			}
		}
		// If the mark is already pointed to from here,
		else
			FREE( prevMark );
		FREE( newMark );
		// else: If the mark is pointed to already, nothing needs to be done.
		// Increase number of links to this mark.
		exNewMark->nofLinks++;
		return exNewMark;

	}
}

/**
 * Answers whether given candidates array is invalid.
 */
static inline _Bool isInvCArr( candArr cArr )
{
	return (cArr.limit > cArr.cap);
}

/**
 * Compares keys for the data structure holding all repetition marks.
 */
static int compMarkKeys( const void *a, const void *b )
{
	const repMark* markA = (const repMark*) a;
	const repMark* markB = (const repMark*) b;

	unsigned char scoreA = ((markA->tIdx > markB->tIdx) << 2) |
												 ((markA->repPrior > markB->repPrior) << 1) |
												 ((markA->start > markB->start));
	unsigned char scoreB = ((markB->tIdx > markA->tIdx) << 2) |
												 ((markB->repPrior > markA->repPrior) << 1) |
												 ((markB->start > markA->start));
	return (scoreA > scoreB) - (scoreB > scoreA);
}

/**
 * Compares repetition properties pointed to by the arguments.
 * Currently, the properties are weighted (sorted with decreasing weight) 
 * according to these criteria:
 * 		depth order (shallower is better),
 * 		left-right order (more to left is better),
 * 		greediness (greedy is better).
 */
static int compRepProps( const void *a, const void *b )
{
	const annRepProp* annPropA = (const annRepProp*) a;
	const annRepProp* annPropB = (const annRepProp*) b;
	const repProp propA = annPropA->val;
	const repProp propB = annPropB->val;

	// The lower score, the better.
	unsigned char scoreA =
				( (annPropA->oDir == (propA.order > propB.order)) << annPropA->oMagn ) |
				( (annPropA->lDir == (propA.lrOrder > propB.lrOrder)) << annPropA->lMagn ) |
				( (annPropA->gDir == (propA.isGreedy > propB.isGreedy)) << annPropA->gMagn );
	unsigned char scoreB =
				( (annPropB->oDir == (propB.order > propA.order)) << annPropB->oMagn ) |
				( (annPropB->lDir == (propB.lrOrder > propA.lrOrder)) << annPropB->lMagn ) |
				( (annPropB->gDir == (propB.isGreedy > propA.isGreedy)) << annPropB->gMagn );
	return (scoreA > scoreB) - (scoreB > scoreA);
}

/**
 * Compares two candidates.
 * 	Beware, though: this is not a standard comparison function. First, it takes 
 * one more argument than `comparison_fn_t', and, second, it does NOT return 0
 * when the candidates are same. All in all, it has very specific return values.
 *
 * Arguments:
 * 	cand1, cand2	: the candidates to compare
 * 	rress					: the regex analysis resources
 *
 * Returns:
 *   2 ... if the first candidate is better
 *  -2 ... if the second candidate is better
 *   1 ... if the candidates are not comparable, and the first one is first in 
 *   				standard ordering (with respect to `start')
 *  -1 ... if the candidates are not comparable, and the second one is first in 
 *  				standard ordering (with respect to `start')
 *   0 ... if the candidates are not comparable and have the same `start'
 *   7 ... if the candidates are same
 */
static inline int compCands( const cand *const cand1, const cand *const cand2,
														 const rxAnaRess *const rress )
{
	int retVal;
	// Use the smaller candidate, regarding `start'.
	if( cand1->start != cand2->start )
	{
		if( cand1->start < cand2->start )
			return 1;
		else
			return -1;
	}
	// If `start' is same for both candidates, decide based on the history.
	else
	{
		h_idx hIdx;
		h_elm *hElm1, *hElm2;
		_Bool isGreedy;
		unsigned int maxReps;
	  /* Implicit setting for the case that the candidates are identical. */
		retVal = 7;

		for( hIdx = rress->nofReps - 1; hIdx != negHIdx; hIdx-- )
		{
			hElm1 = &cand1->hist[ hIdx ];
			hElm2 = &cand2->hist[ hIdx ];
			if( hElm1->isOpen != hElm2->isOpen )
				return 0;

			// Both candidates have to have used this rep. to be distinguishable.
			if(	hElm1->used && hElm2->used )
			{
#ifdef DEBUG
				assert( ( hElm1->mark == NULL ) == ( hElm2->mark == NULL ) );
#endif
				maxReps = rress->repProps[ hIdx ].maxReps;
				// If the candidates differ in the counts of rep.s,
					// If exactly one of them may have unbounded number of repetitions, and 
					// it is an advantage, and neither count of repetitions reached is 
					// maximal possible,
				if( (isGreedy = rress->repProps[ hIdx ].isGreedy) &&
							hElm1->unbounded != hElm2->unbounded &&
							maxReps &&
							hElm1->repCnt < maxReps &&
							hElm2->repCnt < maxReps )
					retVal = hElm1->unbounded ? 2 : -2;
				// Or if they differ in number of repetitions,
				else if( hElm1->repCnt != hElm2->repCnt )
					retVal = (hElm1->repCnt > hElm2->repCnt) == isGreedy ? 2 : -2;
				// Or they don't differ at this rep. op.
				else
					continue;

#ifdef DEBUG
				assert( hElm1->isOpen == hElm2->isOpen );
#endif
				// If the candidates have this rep. open and differ at it, they are 
				// incomparable, unless max count of repetitions is unbounded for the 
				// rep. op.
				if( hElm1->isOpen && maxReps )
					return 0;
			}
		}
	}
	return retVal;
}


static inline unsigned char parseOctal( wchar_t a, wchar_t b, wchar_t c )
{
	 return (unsigned char) (
				 (((wctob( a ) << 3) + wctob( b )) << 3) + wctob( c ));
}

static inline unsigned char parseHexa( wchar_t a, wchar_t b )
{
	 return (unsigned char) ((wctob( a ) << 4) + wctob( b ));
}

/**
 * Simply parses an unsigned integer from a wide chars string.
 *
 * Arguments:
 * 	 str : the string
 * 	 pos : position in the string where to start parsing
 *
 * Returns: the uint parsed (may overflow) or 0 if no wchars could be parsed as 
 * an uint.
 *
 * Side effect: the `pos' pointer is left pointing to the first wchar which 
 * could not be parsed, possibly just after the last wchar in str, if all the 
 * rest of str could be parsed as an uint.
 */
static inline unsigned int parseUInt( const wchar_t* str, r_idx *pos )
{
	unsigned int theInt = 0;
	size_t strLen = wcslen( str );
	int letter;
	while( *pos < strLen )
	{
		letter = wctob( str[ *pos ] );
		if( '0' <= letter && letter <= '9' )
		{
			theInt = 10*theInt + (letter - '0');
			(*pos)++;
		}
		else
			break;
	}
	return theInt;
}

/**
 * Answers whether the given node represents an opening parenthesis.
 * Assumes the argument is not null.
 */
static inline _Bool isOpeningPar( node* node )
{
	return (node->op == cat && node->atom == NULL);
}

/**
 * Answers whether the given node represents a dot ('.'), the allways-matching 
 * symbol.
 */
static inline _Bool isDot( node* node )
{
	return (node->op == cat && node->atom &&
					!node->atom->size && !node->atom->propsSize);
}

// FIXME (optional) Make a set of chars from collection, in enumerating using 
// `[]'.
// TODO (optimisation) index conjunctions, and, during evaluating each input 
// character, collect all possible starts of candidates in the conjunction and 
// throw away those missing from one or more of the members of the conjunction
// TODO Throw more different kinds of exceptions instead of one common one.

// TODO (documentation) Mention the effect of {.,0} as unbounded number of 
// repetitions.

// vim: set ts=2 fdm=syntax :
